11
$\begingroup$

Let $c(n,k)$ be the unsigned Stirling numbers of the first kind, i.e., the number of $n$-permutations with exactly $k$ cycles. Apparently, $$\sum_{k=1}^n c(n,k)2^k = (n+1)!$$

I want to prove the equality.

I am most interested in a combinatorial explanation.

The exponential generating function for the RHS is $\frac1{(1-x)^2}$. Is there a way to derive the e.g.f. for the LHS symbolically?

$\endgroup$
3
$\begingroup$

By way of enrichment here is a proof using generating functions. Suppose we seek to evaluate $$\sum_{k=1}^n \left[n\atop k\right] 2^k.$$

The species of decompositions of permutations into cycles marked by the number of cycles is $$\mathfrak{P}(\mathcal{U}\mathfrak{C}(\mathcal{Z})).$$ This gives the generating function $$G(z, u) = \exp\left(u\left(\log\frac{1}{1-z}\right)\right)$$ which immediately yields $$\left[n\atop k\right] = n! [z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

This gives for the sum $$n! [z^n] \sum_{k=1}^n 2^k \times \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

The term at $k=0$ does not contribute so we may include it to get $$n! [z^n] \sum_{k=0}^n 2^k \times \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

Furthermore $\log\frac{1}{1-z}$ starts at $z$ and $\left(\log\frac{1}{1-z}\right)^k$ starts at $z^k$ so we may extend the sum to infinity, getting $$n! [z^n] \sum_{k=0}^\infty 2^k \times \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

This is $$n! [z^n] \exp\left(2\log\frac{1}{1-z}\right) = n! [z^n] \frac{1}{(1-z)^2}.$$ This finally yields $$n! {n+1\choose n} = (n+1)!$$

Addendum. The proof by @QuiaochuYuan is remarkably elegant. Suppose you are distributing $Q$ colors into $n$ slots (initially creating $Q^n$ possible configurations) and want to count orbits under the action of the symmetric group $S_n$ (all $n!$ permutations) on the slots. By Burnside you need to average the number of colorings fixed by a given permutation $\sigma$ over all $n!$ permutations. But a permutation with $k$ cycles fixes $Q^k$ colorings (color must be constant on a cycle). Therefore the number of colorings is given by

$$\frac{1}{n!} \sum_{k=1}^n \left[n\atop k\right] Q^k.$$

On the other hand lining up the colors according to some order we have by stars-and-bars that there are $${n+Q-1\choose Q-1}$$ colorings, thus completing the proof.

$\endgroup$
7
$\begingroup$

The more general result is that

$$\sum_{k=1}^n c(n, k) x^k = x(x + 1) \dots (x + n - 1).$$

Your result follows straightforwardly by substituting $x = 2$. This identity has the following cute proof: dividing both sides by $n!$ we get

$${x + n - 1 \choose n} = \frac{1}{n!} \sum_{k=1}^n c(n, k) x^k.$$

The LHS is the number of multisets of size $n$ on a set of size $x$. This is the number of orbits of the action of the symmetric group $S_n$ on the set of functions from a set $[n]$ of size $n$ to a set $[x]$ of size $x$, and accordingly the number of orbits can be counted using Burnside's lemma. If $\sigma$ is a permutation with $k$ cycles, then the number of fixed points of $\sigma$ acting on functions $[n] \to [x]$ is $x^k$, and the conclusion follows.

You can also prove this identity by induction on $n$.

For more general results along these lines see this blog post and this one.

$\endgroup$
  • 1
    $\begingroup$ Very nice work. (+1). $\endgroup$ – Marko Riedel Mar 12 '15 at 22:25
  • $\begingroup$ For kicks, here's a sketch of the proof by induction. Think of permutations as total orders, and so think of building permutations in $S_n$ from permutations in $S_{n-1}$ by inserting $n$ somewhere in a total order of $\{ 1, 2, \dots n-1 \}$. Exactly one way of doing this puts $n$ in its own cycle; the other $n - 1$ ways put $n$ in some other cycle. So the generating function for $S_{n-1}$ is $(x + n - 1)$ times the generating function for $S_n$. $\endgroup$ – Qiaochu Yuan Mar 12 '15 at 22:28
  • $\begingroup$ This appears to be true. We ask how we can join $n+1$ to a permutation of $[n]$ decomposed into cycles. It could either be a fixed point (giving a new cycle and hence a multplier of $x$) or it could be inserted somewhere on the existing cycles in one of $n$ available slots / midpoints of an edge, giving the multiplier $n.$ The result follows. $\endgroup$ – Marko Riedel Mar 12 '15 at 22:45
4
$\begingroup$

Here is a tedious but extremely elementary combinatorial argument for the more general result.

Let $\pi$ be a permutation of $[n]$ having $k$ cycles. The standard representation of $\pi$ is

$$(a_{11}a_{12}\ldots a_{1m_1})(a_{21}a_{22}\ldots a_{2m_2})\ldots(a_{k1}a_{k2}\ldots a_{km_k})\;,\tag{1}$$

where $a_{i1}>a_{ij}$ for $i=1,\ldots k$ and $j=2\ldots,m_i$, and $a_{11}<a_{21}<\ldots a_{k1}$. In other words, each cycle is listed with its largest element first, and the cycles are listed in increasing order of their largest elements. One-element cycles are not suppressed. The map that sends $\pi$ to the permutation whose one-line representation is $(1)$ without the parentheses is a bijection.

Now we’ll count the permutations $\pi$ with $k$ cycles as in $(1)$. Clearly $a_{k1}=n$, but we have a free choice for $a_{11},a_{21},\ldots,a_{k-1,1}$. Once they’re chosen, in how many ways can we fill out $(1)$? We can ignore the parentheses, and of course we have to put $a_{11}$ in the first slot. We now place the $a_{11}-1$ elements of $[n]$ that are less than $a_{11}$; they can go anywhere in $(1)$ after $a_{11}$ so they can be placed in $(n-1)(n-2)\ldots(n-a_{11}+1)$ different ways. Once they’ve been placed, $a_{21}$ must go in the first free slot. That leaves $n-a_{11}-1$ open slots in $(1)$, and the $a_{21}-a_{11}-1$ elements of $[n]$ that are larger than $a_{11}$ and smaller than $a_{21}$ can go in any of them. Thus, they can be placed in

$$(n-a_{11}-1)(n-a_{11}-2)\ldots(n-a_{21}+1)$$

different ways, after which $a_{31}$ must be placed in the first available slot.

In general, once we’ve made the forced placement of $a_{i1}$, the $a_{i1}-a_{i-1,1}-1$ elements of $[n]$ lying strictly between $a_{i-1,1}$ and $a_{i1}$ can be placed in

$$(n-a_{i-1,1}-1)(n-a_{i-1,1}-2)\ldots(n-a_{i1}+1)$$

different ways. Thus, if we set $a_{01}=0$, the number of permutations with these values of $a_{11},\ldots,a_{k1}$ is

$$\prod_{i=0}^{k-1}(n-a_{i-1,1}-1)(n-a_{i-1,1}-2)\ldots(n-a_{i1}+1)=\frac{(n-1)!}{\prod_{i=1}^{k-1}(n-a_{k1})}\;.\tag{2}$$

As we run over all possible choices for the leading elements $a_{11},\ldots,a_{k1}$, the denominator in $(2)$ runs over all $(k-1)$-fold products of distinct elements of $[n-1]$, so $(2)$ itself runs over all $(n-k)$-fold products of distinct elements of $[n-1]$, and $n\brack k$ is therefore the sum of all such products.

However, that sum is clearly also the coefficient of $x^k$ in the product

$$x^{\overline n}=\prod_{i=0}^{n-1}(x+i)=x(x+1)(x+2)\ldots(x+n-1)\;,$$

so in general we have the identity

$$x^{\overline n}=\sum_{k=0}^n{n\brack k}x^k\;,$$

and the desired identity follows by setting $x=2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.