Here is a bit of combinatorics I encountered when preparing a paper on the co-evolution of behavioral repertoire, brain size, and lifespan (I will talk about the paper another time…). Let’s begin with two definitions:
Definition 1: The falling power
is defined as the product
, or:
(1) 
If you are familiar with binomial coefficients, they are related to falling powers by
.
Definition 2: The Stirling numbers of the second kind are a double series of numbers that tell us how many ways there are to partition
objects into
non-empty subsets. This is written sometimes
and sometimes
. I will use the fancier notation. For example, there are only 3 ways to partition 3 elements in to 2 non-empty subsets: (12)(3), (13)(2), (1)(23), where
means that
and
have been put together in the same subset. These numbers, beyond the simplest case, are nowhere near intuitive (at least to me). For example, There are 7 ways to partition 4 objects into 2 subsets, hence
(you can figure these ways out for yourself), and 1701 ways to partition 8 objects in 4 subsets, hence
(I suggest you do not try this on your own).
Now, it happens that falling powers and Stirling numbers of the second kind are related by the following identity:
(2) 
I have only seen this equation proved by induction, but working on the above-mentioned paper I stumbled upon a direct proof that goes as follows. Note first that
is the number of ways to arrange
objects in sequences of length
, with repetitions possible (by sequence I mean an ordered selection so that (1,2,2) and (2,1,2) are two different sequences). So we have
(4) 
Equation (2) then comes from the fact that its r.h.s. is a different (and more laborious) way to count the same sequences. In other words, we can first count the sequences that we can form using only
out of the
objects, and then sum over
:
(5) 
Now we have to calculate the expression in the sum. Consider thus constructing a sequence of length
out of
distinct object, which in turn have been selected among
. There are
ways of selecting which of the
objects are going to be part of the sequence, given that the first object out of
, the second out of
, and so on, until the
-th object can be selected out of
. Once we have the
objects, in how many ways we can allocate them among the
places of the sequence? This is exactly the number of ways in which a set of size
can be partitioned in
non-empty subsets, or, if you want, the number of ways in which
balls can be placed in
bins without leaving any one bin empty. Thus
(6) 
which, together with (5), gives (2).