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).

2 responses to “An identity on falling powers

  1. Darek 2013/09/23 at 15:22

    The third identity is NOT TRUE. I suspect the second one is false as well (though might be wrong as have not checked rigorously). To see that (2) is false, take n=2 and m=2. Then LHS = 4 and RHS = 9.

    • drghirlanda 2013/09/23 at 21:42

      Thanks for pointing out a mistake in identity (3). It should have been (n+1) rather than n on the LHS. I have deleted that part as it was not that interesting anyway. Equation (2), however, should be correct. For example you find it as Theorem 4.1 here.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: