Suppose raindrops are falling on your head, randomly and independently, at an average rate of one per minute. What's the average of the 𝑐𝑢𝑏𝑒 of the number of raindrops that fall on your head in one minute?
The probability that (k) raindrops fall on your head in a minute is given by the Poisson distribution of mean 1, so it's
[ \frac{1}{ek!} ]
I could explain this but let's move on. The puzzle asks us to compute the expected value of (k^3) for this probability distribution, which is
[ \sum_{k=0}^\infty \frac{k^3}{ek!} ]
The heart of the puzzle is to figure out this sum. It turns out that
[ \sum_{k = 0}^\infty \frac{k^n}{k!} = B_n e ]
where (B_n) is the (n)th 'Bell number': the number of partitions of an (n)-element set into nonempty subsets. This is called 'Dobiński's formula'. I'll prove it in my next post. Now let's just use it!
We're interested in the case (n = 3). There are 5 partitions of a 3-element set
[ {{1,2,3}}, ]
[ {{1,2}, {3}}, ; {{2,3}, {1}}, ; {{3,1}, {2}}, ]
[ {{1}, {2}, {3}} ]
so (B_3 = 5).
So, the average of the cube of the number of raindrops that fall on your head in one minute is 𝟓.
Wild, huh? From probability theory to combinatorics.
To prove Dobiński's formula we can use combinatorial species and their generating functions.
There's a species (\mathrm{Part}), such that (\mathrm{Part}(n)) is the set of partitions of an (n)-element set into nonempty subsets. By definition its generating function is
[ \displaystyle{
|\mathrm{Part}|(x) =
\sum_{n \ge 0} \frac{|\mathrm{Part}(n)|}{n!} x^n =
\sum_{n \ge 0} \frac{B_n}{n!} x^n } ]
since we call the cardinality (|\mathrm{Part}(n)|) the (n)th Bell number.
To put a partition on a finite set amounts to chopping it into a finite set of nonempty finite sets, so using a cool fact about species, we have
[ |\mathrm{Part}| = |\mathrm{Exp}| \circ |\mathrm{NE}| ]
where (\mathrm{Exp}) is the species 'being a finite set' and (\mathrm{NE}) is the species 'being a nonempty finite set'. There's one way for an (n)-element set to be a finite set so
[ |\mathrm{Exp}|(x) = \sum_{n \ge 0} \frac{x^n}{n!} = e^x ]
and similarly
[ |\mathrm{NE}|(x) = \sum_{n \ge 1} \frac{x^n}{n!} = e^x - 1 ]
Thus we have
[ |\mathrm{Part}|(x) = e^{e^x - 1} ]
and thus
[ \sum_{n \ge 0} \frac{B_n}{n!} x^n = e^{e^x - 1} ]
Now let's use this to prove Dobiński's formula! We start by calculating the right hand side another way. We have
[ \displaystyle{ e^{e^x} = \sum_{k \ge 0} \frac{e^{kx}}{k!}
= \sum_{k \ge 0} \frac{1}{k!} \sum_{n \ge 0} \frac{(kx)^n}{n!} }]
so
[ \displaystyle{ e^{e^x - 1} =
\frac{1}{e} \sum_{k \ge 0} \frac{1}{k!} \sum_{n \ge 0} \frac{(kx)^n}{n!}} ]
The coefficient of (x^n) in this power series must be (B_n/n!), so Dobiński's formula follows:
[ \displaystyle{ B_n = \frac{1}{e} \sum_{k = 0}^\infty \frac{k^n}{k!} } ]
Or if you're really brave, just dive in and see how I apply them to random permutations. In learning about these, I learned something really surprising to me: random permutations are largely governed by the Poisson distribution. That got me interested in combinatorial proofs of Dobiński's formula. Besides the proof I just gave you, there's a nice proof due to Rota that uses Stirling numbers:
@johncarlosbaez
Usually I would assume that any books you mention are going to be over my head, but as it turns out, I've read and studied the third one, "Generatingfunctionology" by Herbert Wilf, and I would encourage people to take a look at that one at least.
I found it to be very clear and (as math books go) easy to understand. The author's approach to writing impressed me; I don't often feel that way about math books.
And the subject of generating functions is a hugely important tool for one's toolbox.
The second book I haven't read, but I've read another by those two authors (Philippe Flajolet and Robert Sedgewick), "An Introduction to the Analysis of Algorithms", and I liked it, so I will probably like this one as well ("Analytic Combinatorics").
Wikipedia: Flajolet "introduced the theory of analytic combinatorics". I know Sedgewick from a lot of famous work in computer science, during and after being a grad student of Donald Knuth. "He solved open problems left by Donald Knuth...His books on algorithms[20] are replete with novel implementations of classic algorithms and scientific studies comparing them"
So there's some potential encouragement for other fans of computer science.
Edit: the first one, by François Bergeron, Gilbert Labelle, and Pierre Leroux" begins:
'...the modern notion of function ... has been made independent of any actual description format. A similar process ... introduce in combinatorics the notion of “Species” to make the description of structures independent of any specific format... serves as an elegant “explanation” for the surprising power of generating function uses for the solution of structure enumeration"'
@dougmerritt - I'm glad you know 𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑖𝑛𝑔𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛𝑜𝑙𝑜𝑔𝑦 - it's a blast. Flajolet's book is also lots of fun, full of concrete examples of how to use generating functions. I think it gently brings in the fact that what you're computing an (exponential) generating function 𝑜𝑓 is actually a species: a functor from the groupoid of finite sets to Set, sending each finite set to some set of structures you can put on it. The book by Bergeron, Labelle, and Leroux digs a bit deeper into the functorial approach to species. But none of these gets anywhere near the full glory of that viewpoint.... you'll probably be relieved to know. I got into that more deeply in this course:
@johncarlosbaez one thing I like about this is that we can deduce from the Dobinsky formula the Wyman Moser asymptotic for Bell numbers. The strategy isn't obvious : the serie isn't monotone so you've to find the largest term and approximate the serie by a Gaussian integral centered on this maximum andusing the rectangle method ! So the proof relies on basic mathematical methods but the result is impressive 😁
@uxor - nice, I don't know the Wyman Moser asymptotic formula, but it sounds like a fun example of approximating something by a Gaussian, and I bet there is a lot of deep combinatorial significance lurking beneath it.
Add comment