# drghirlanda

Computational behavior theory and cultural evolution

## An identity on falling powers

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 $n^{\underline{m}}$ is defined as the product $n(n-1)\cdots(n-m+1)$, or:

(1)    ${\displaystyle n^{\underline{m}}=\prod_{i=1}^m (n-i+1)}$

If you are familiar with binomial coefficients, they are related to falling powers by $n^{\underline m} = m! {n \choose m}$.

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 $n$ objects into $k$ non-empty subsets. This is written sometimes $S(n,k)$ and sometimes $\left\{n\atop k\right\}$. 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 $(xy)$ means that $x$ and $y$ 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 $\left\{4\atop 2\right\}=7$ (you can figure these ways out for yourself), and 1701 ways to partition 8 objects in 4 subsets, hence $\left\{8\atop 4\right\}=1701$ (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)    ${\displaystyle n^m = \sum_{k=0}^m\left\{m\atop k\right\}n^{\underline k}}$

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 $n^m$ is the number of ways to arrange $n$ objects in sequences of length $m$, 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)    $\mbox{\# different sequences of }m\mbox{ objects chosen with repetition among }n = n^m$

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 $k$ out of the $n$ objects, and then sum over $k$:

(5)    ${\displaystyle n^{m} = \sum_{k=0}^n \mbox{\# different sequences of }m\mbox{ objects using any }k\mbox{ objects out of }n}$

Now we have to calculate the expression in the sum. Consider thus constructing a sequence of length $m$ out of $k$ distinct object, which in turn have been selected among $n$. There are $n^{\underline k}$ ways of selecting which of the $k$ objects are going to be part of the sequence, given that the first object out of $n$, the second out of $n-1$, and so on, until the $k$-th object can be selected out of $n-k+1$. Once we have the $k$ objects, in how many ways we can allocate them among the $m$ places of the sequence? This is exactly the number of ways in which a set of size $m$ can be partitioned in $k$ non-empty subsets, or, if you want, the number of ways in which $m$ balls can be placed in $k$ bins without leaving any one bin empty. Thus

(6)    ${\displaystyle \mbox{\# different sequences of }m\mbox{ objects using any }k\mbox{ objects out of }n} = \left\{m\atop k\right\} n^{\underline k}$

which, together with (5), gives (2).