A Combinatorial Proof of a Stirling Number Formula

One of the fundamental properties of the (unsigned) Stirling numbers of the first kind is that they can be used to convert from rising factorial powers to ordinary powers via the formula \displaystyle x^{\overline{n}} = \sum_{k=0}^n \left[ n \atop k \right] x^k.  This post gives a combinatorial proof of this formula.

Suppose we can color the numbers in a permutation according to cycle (i.e., numbers in the same cycle are the same color). We can color two different cycles the same color. If there are n elements to permute and x colors, how many of these cycle-colored permutations are there?

One way to count them is to condition on the number of cycles. There are \left[ n \atop k \right] ways to choose a permutation on [n] with k cycles, and there are x^k ways to color the k cycles once chosen. So the answer is \displaystyle \sum_{k=0}^n \left[ n \atop k \right] x^k.

Another way to count them is to consider the elements 1, 2, \ldots, n in turn.  First, color the number 1 in x ways.  Then the number 2 can either start a new colored cycle, in x ways, or go after 1 in 1’s cycle, in 1 way. So there are x + 1 choices for the number 2.  The number 3 can start a new colored cycle, in x ways, or go immediately after 1 or 2 in their cycles, in 2 ways. So there are x + 2 choices for the number 3.  In general, there are there are x+k-1 choices for where to place the number k.  Thus there are x(x+1) \cdots (x+n-1) = x^{\overline{n}} choices for placing the n elements in order to create a cycle-colored permutation.

This argument assumes that x is a positive integer.  To extend the proof for all real numbers, note that the formula \displaystyle x^{\overline{n}} = \sum_{k=0}^n \left[ n \atop k \right] x^k is a polynomial in x of degree n.  Since we have shown that this expression holds for infinitely many values of x (the positive integers), it must hold for all real values of x.

(A variant of this argument appears in the second edition of Volume 1 of Richard Stanley’s Enumerative Combinatorics, pp. 33-34.)

Advertisements
This entry was posted in combinatorics, Stirling numbers. Bookmark the permalink.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s