Blog

In this post I'd like to talk about the catchily named Stirling numbers of the second kind, which I first encountered in this Maths Stack Exchange post. I'll start with some motivation for Stirling numbers of the second kind, show how they can be recursively calculated, and then show some interesting features of these numbers.

Suppose a fair die has \(f\) distinct faces, and suppose you roll it \(n\) times. What's the probability that you roll exactly \(k\) distinct faces? Since the die is fair, each sequence of rolls is equally likely, so the probability is given by

The number of possible sequences of \(n\) rolls is just \(f^{n}\). And since, if we see exactly \(k\) distinct faces, the \(k\) distinct faces are equally likely to be any of the subsets of size \(k\) out of \(f\). So we have:

Let's think about breaking down the \(n\) rolls into \(k\) subsets based on which rolls matched each face. For example, if \(k = 3\) and the sequence of rolls was \(\{1, 2, 1, 2, 3, 1\}\), then the three subsets would be \(\{1, 3, 6\}, \{2, 4\}\), and \(\{5\}\), where the first subset is \(\{1, 3, 6\}\) because rolls 1, 3, and 6 were face 1. Since each of the \(k\) faces was observed, each subset must be non-empty. Any permutation of these subsets still creates a valid sequence of observations, e.g. if we swapped the first two subsets then the subsets would correspond to the sequence of rolls \(\{2, 1, 2, 1, 3, 2\}\). And since there are \(k!\) to permute the subsets, we have that the probability is

The number of ways to partition \(n\) items into \(k\) non-empty subsets is a Stirling number of the second kind, denoted \(\left\{n\atop k\right\}\).

In the same way that the factorial function is technically defined recursively, $$ x! = \begin{cases} 1 & \text{if } x = 0,\\ (x - 1)! \thinspace x & \text{if } x > 0, \end{cases} $$ we can define the Stirling number of the second kind recursively. If \(n = 0\) and \(k = 0\), then the probability of seeing \(k\) distinct numbers in \(n\) rolls is 1, so we set \(\left\{0\atop 0\right\} = 1\). If \(n \geq 1\) then we are guaranteed to see at least \(1\) distinct face, so \(\left\{n\atop 0\right\} = 0\). If \(n = 0\) and \(k\geq1\), then seeing \(k\) faces is impossible, so \(\left\{0\atop k\right\} = 0\). And if \(k > n\) then seeing \(k\) distinct faces in \(n\) rolls is impossible, so \(\left\{n\atop k\right\} = 0\). These give us the base cases for a recursion. The recursive formula for \(n, k \geq 1\) is given by

To see why, consider splitting \(n\) items into \(k\) non-empty subsets, and suppose that \(n - 1\) of the items have already been added to subsets. We will consider two cases. In one case, the \(n - 1\) items have only been assigned to \(k - 1\) subsets (making each of these \(k-1\) subsets non-empty) and we are forced to use the \(n\)th item to make the \(k\)th subset non-empty. There are \(\left\{n-1\atop k-1\right\}\) ways that \(n-1\) items can be assigned to make \(k-1\) non-empty subsets, hence the first term in the sum. In the second case, the \(n-1\) items have already been assigned to all \(k\) subsets (making each of the \(k\) subsets non-empty), and we are free to choose which of the \(k\) subsets to put the \(n\)th item in. There are \(\left\{n-1\atop k\right\}\) ways that \(n-1\) items can be assigned to make \(k\) non-empty subsets, and \(k\) choices for the \(n\)th item, hence the second term in the sum.

The plot shows a "Pascal's triangle" for the Stirling numbers of the second kind, which I call "Stirling's second triangle". The top square is \(\left\{0\atop 0\right\}\), the next row contains \(\left\{1\atop 0\right\}, \left\{1\atop 1\right\}\), and so on.

You can see how the generating rule differs from the one for \(\binom nk\). Instead of $$ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} $$ we have our recursive formula. Let's do the 5th row (corresponding to \(n = 4\)) as an example. We know from the base cases that \(\left\{4\atop 0\right\} = 0\). Then \(\left\{4\atop 1\right\} = 0 + 1 \times 1 = 1\), \(\left\{4\atop 2\right\} = 1 + 2 \times 3 = 7\), \(\left\{4\atop 3\right\} = 3 + 3 \times 1 = 6\), and \(\left\{4\atop 4\right\} = 1 + 4 \times 0 = 1\).

The diagonals in this triangle have some interesting features. Consider the diagonal \(\left\{2\atop 2\right\}\), \(\left\{3\atop 2\right\}\), \(\left\{4\atop 2\right\}\), \(\left\{5\atop 2\right\}\), \(\left\{6\atop 2\right\}\), ... = 1, 3, 7, 15, 31, ... = \(2^1 - 1\), \(2^2 - 1\), \(2^3 - 1\), \(2^4 - 1\), \(2^5 - 1\), ... The triangular numbers 0, 1, 3, 6, 10, 15, ... also make an appearance. I will leave it as an exercise for the reader to show that

Finally, an interesting feature occurs if you shade in the "Stirling's second triangle" according to the parity of the entry. Let the odd numbers be shaded grey and the white numbers be shaded white. At first it is difficult to discern a pattern, but it a fractal pattern related to the Sierpiński triangle emerges.

It's 2021, and the Advent calendar has disappeared, so it's time to reveal the answers and annouce the winners. But first, some good news: with your help, Santa received all his letters and Christmas was saved!

Now that the competition is over, the questions and all the answers can be found here. Before announcing the winners, I'm going to go through some of my favourite puzzles from the calendar, reveal the solution and a couple of other interesting bits and pieces.

My first highlight is this puzzle from 5 December, that I think doesn't seem obvious that there's even a unique answer until you spot some nice properties of dice.

My next highlight is the puzzle from 15 December. I had a lot of fun trying to write this one. At the end, I tell you that T represents 4: this puzzle still has a unique answer without this, but it was too hard to get started.

My next highlight is the puzzle from 16 December. I had a lot of fun writing this one too. At least a few people seem to have enjoyed solving it, as indicated by this comment.

My final highlight is the puzzle from 21 December. My method for solving this one was quite complicated. Let me know in the comments or on Twitter if you have a better way of solving it.

Once you've entered 24 answers, the calendar checks these and tells you how many are correct. I logged the answers that were sent for checking and have looked at these to see which puzzles were the most and least commonly incorrect. The bar chart below shows the total number of incorrect attempts at each question.

You can see that the most difficult puzzles were those on 6, 14, 19, 21, and 24 December; and the easiest puzzles were on 3, 9, 10, 16, and 17 December.

The solutions to all the individual puzzles can be found here. If you want to read some alternative solutions to the puzzles, you can find Alira's solutions here, including a very nice explanation of how the final clues fit together to find the directions to Santa's house.

Using the daily clues, it was possible to work out that Santa's house could be found by following the directions 3,7,1,1,4,3,3,4,9,3,3,9 on this map.

Due to the way the Advent compass worked, there are actually a few different ways to get to Santa's house. For example, 7,5,7,1,1,4,3,3,4,9,3,3 also gets you there:

I'll leave you to work out how many different ways there are to get there...

Here's the full collection of tiles that you could find by walking around the map:

And finally (and maybe most importantly), on to the winners: 223 people found Santa's house entered the competition. This is quite a lot more than in previous years:

From the correct answers, the following 10 winners were selected:

Congratulations! Your prizes will be on their way shortly.

The prizes this year include 2020 Advent calendar T-shirts. If you didn't win one, but would like one of these, I've made them available to buy on Teespring alongside the T-shirts from previous years.

Additionally, well done to 4nder, Ashley Frazer Jarvis, Aaron Stiff, Alan Buck, Alejandro Villarreal, Alex Bolton, Alex Davis, Alex Klapheke, Alexander Rakitin, Anders Kaseorg, Andrew, Andrew P Turner, Andy Ennaco, Annabel, Anthony Della Pella, Artie Smith, Athena, Austin, Austin Shapiro, Beau Ferguson, Becky Russell, Ben Buchwald, Ben Jones, Ben Reiniger, Benjamin Tozer, Bennet, Beth Jensen, Blake, Brennan Dolson, Brian Carnes, Brian Wellington, Burak Kadron, Caleb Likely, Callum Hobbis, Carl Westerlund, Carmen Günther, Cath Simpson, Cathy Hooper, Chris Hellings, Christy Hales, Colin, Colin Brockley, Connie, Corbin Groothuis, Cory Peters, Cosmo Viola, Dan Colestock, Dan DiMillo, Dan McIntyre, Dan Whitman, Dana Sussman, Daniel De la Paz, David, David Ault, David Berardo, David Fox, David Kendel, David Mitchell, David Parmenter, David and Ivy Walbert, Dean Thomas, Deborah Tayler, Don Anderson, Donagh Collins, Elizabeth Blackwell, Emilie Heidenreich, Emily Troyer, Eric Kolbusz, Eric Skoglund, Erik Eklund, Eva, Evan Louis Robinson, Fionn Woodcock, Frances Haigh, Frank Kasell, Franklin Ta, Fred Verheul, Georges, Gabriella Pinter, Gert-Jan de Vries, Graham Greve, Gregory Loges, Gwendal Collet, Harry Allen, Heerpal Sahota, Helen, Helen Matthews, Herschel Pecker, Håkon Balteskard, Ivan Arribas, Jacob Young, James Demers, James Laver, Jan, Jason Demers, Jason Kass, Jean-Sébastien Turcotte, Jeff Rubin, Jefff Michael, Jen Huang, Jessica Marsh, Jim Rogers, Joe Gage, Johan Asplund, John Alasdair Warwicker, Jon Foster, Jon Lipscombe, Jon Palin, Jonathan Chaffer, Jonathan Forsythe, Jonathan Winfield, Jordan Susskind, Jorge del Castillo, Kai Lam, Karen Climis, Keith Pound, Ken Cheung, Killeen, Kristen Koenigs, Kristin Gramza, Kurt Engleman, Laura Midgley, Lauren Woolsey, Lewis Dyer, Linus Banghart-Linn, Liz Madisetti, Louis de Mendonca, Magnus Eklund, Mark Stambaugh, Martijn O., Martin Harris, Martin Holtham, Martine Nome, Matt Askins, Matt Hutton, Matthew Reynier, Matthew Riggle, Matthew Schulz, Matthew Scroggs, Matthias Planitzer, Maxime Rivet, Maximilian Pfister, Michael DeLyser, Michael Prescott, Mihai Zsisku, Mike Hands, Moritz Stocker, Nadine Chaurand, Nathan Chun, Nick C, Nick Keith, Nick Mohr, Norvin Richards, Olov Wilander, Pamela Docherty, Pau Batlle, Paul Livesey, Pranshu Gaba, Ray Arndorfer, Rea, Reuben Cheung, Riccardo Lani, Richard Pemberton, Rileigh Luczak, Road White, Roni, Rosie Paterson, Russ Collins, Ruth Franklin, Ryan Coomer, Ryan Seldon, Ryan Wise, Sam Dreilinger, Sam Hartburn, Sammie Buzzard, Sara Van Hoy, Sarah Brook, Saul Freedman, Scott, Sean, Sean Carmody, Sean Henderson, Sean McDonald, Sebastian, Selina Glauert, Seth Cohen, Shivanshi Adlakha, Simon Schneider, Sophie Maclean, Spencer B., Stephen Cappella, Stephen Dainty, Stephen Jasina, Steve Blay, Steve Paget, Steven Richardson, Susana Early, Tarim, Tim Holman-Wilkens, Tim Lewis, Todd Geldon, Tom Fryers, Tony Mann, Tristan Shephard, Valentin Valciu, Vinesh, Yasha, Yuliya Nesterova, Yurie Ito, and Zachary Polansky who all also found Santa's house but were too unlucky to win prizes this time.

See you all next December, when the Advent calendar will return.

In November, I spent some time designing this year's Chalkdust puzzle Christmas card.

The card looks boring at first glance, but contains 9 puzzles. By splitting the answers into two digit numbers, then colouring the regions labelled with each number (eg if an answer to a question in the red section is 201304, colour the regions labelled 20, 13 and 4 red), you will reveal a Christmas themed picture.

If you want to try the card yourself, you can download this pdf. Alternatively, you can find the puzzles below and type the answers in the boxes. The answers will be automatically be split into two digit numbers, and the regions will be coloured...

This year, the front page of mscroggs.co.uk will once again feature an Advent calendar, just like in the five previous Decembers. Behind each door, there will be a puzzle with a three digit solution. The solution to each day's puzzle forms part of a logic puzzle:

It's nearly Christmas and something terrible has happened: you've just landed in a town in the Arctic circle with a massive bag of letters for Santa, but you've lost to instructions for how to get to Santa's house near the north pole. You need to work out where he lives and deliver the letters to him before Christmas is ruined for everyone.

Due to magnetic compasses being hard to use near the north pole, you brought with you a special Advent compass. This compass has nine numbered directions. Santa has given the residents of the town clues about a sequence of directions that will lead to his house; but in order to keep his location secret from present thieves, he gave each resident two clues: one clue is true, and one clue is false.

The residents' clues will reveal to you a seqeunce of compass directions to follow. You can try out your sequences on this map.

Behind each day (except Christmas Day), there is a puzzle with a three-digit answer. Each of these answers forms part of a resident's clue. You must use these clues to work out how to find Santa's house.

Ten randomly selected people who solve all the puzzles, find Santa's house, and fill in the entry form behind the door on the 25th will win prizes!

The winners will be randomly chosen from all those who submit the entry form before the end of 2020. Each day's puzzle (and the entry form on Christmas Day) will be available from 5:00am GMT. But as the winners will be selected randomly, there's no need to get up at 5am on Christmas Day to enter!

As you solve the puzzles, your answers will be stored. To share your stored answers between multiple devices, enter your email address below the calendar and you will be emailed a magic link to visit on your other devices.

To win a prize, you must submit your entry before the end of 2020. Only one entry will be accepted per person. If you have any questions, ask them in the comments below or on Twitter.

So once December is here, get solving! Good luck and have a very merry Christmas!

A week ago, it was 22 July: Pi Approximation Day. 22/7 (22 July in DD/M format) is very close to pi, closer in fact than 14 March's approximation of 3.14 (M.DD).

During this year's Pi Approximation Day, I was wondering if there are other days that give good approximations of interesting numbers. In particular, I wondered if there is a good 2π (or τ) approximation day.

π is close to 22/7, so 2π is close to 44/7—but sadly there is no 44th July. The best approximation day for 2π is 25th April, but 25/4 (6.25) isn't really close to 2π (6.283185...) at all. The day after Pi Approximation Day, however, is a good approximation of 2π-3 (as π-3 is approximately 1/7). After noticing this, I realised that the next day would be a good approximation of 3π-6, giving a nice run of days in July that closely approximate expressions involving pi.

After I tweeted about these three, Peter Rowlett suggested that I could get a Twitter bot to do the work for me. So I made one: @HappyApproxDay.

@HappyApproxDay is currently looking for days that approximate expressions involving π, τ, e, √2 and √3, and approximate the chosen expression better than any other day of the year. There are an awful lot of ways to combine these numbers, so @HappyApproxDay looks like it might be tweeting quite a lot...