Basic Enumeration once again

Prove the following identity (a):

\sum_{k=0}^{n}\left\{ \begin{array}{c} n \\ k \end{array} \right\}x(x-1)\ldots(x-k+1)=x^{n}

Prove the following identity (b):

\sum_{k=0}^{n}\left [ \begin{array}{c} n \\ k \end{array} \right] = x(x+1)\ldots(x+n-1)

Prove the following identity (c);

\sum_{k=0}^{n}(-1)^{k}\left\{ \begin{array}{c} n \\ k \end{array} \right\}\left[ \begin{array}{c} k \\ j \end{array} \right]= 1, if j=n and is 0, otherwise.

General Hint for all three problems: Please see Wikipedia for Stirling numbers!

Hint (a):

If x is an integer, both sides of the first identity  count mappings of an n element set into an x-element set.

Hint (b):

Both sides count pairs (\pi, \alpha) where \pi is a permutation of an n-element set S, and \alpha is a coloration of S with x colors invariant under \pi.

Hint (c):

Combine the identities in (a) and (b).

Solution (a):

Suppose first that x is a positive integer. Let |X|=x and |N|=n. The number of mappings of N into X is x^{n}. On the other hand, let k denote the cardinality of the range of a mapping of N into X. For k fixed, we can specify in \left\{ \begin{array}{c} n \\ k \end{array} \right\} ways which elements of N are mapped onto the same element of X. Once this partition of N is specified, we have to find an image for each class of it, distinct images for distinct classes. This can be done is x(x-1)\ldots(x-k+1) ways. Thus,

\left\{ \begin{array}{c} n \\ k \end{array}\right\}x(x-1)\ldots(x-k+1)

is the number of mappings of N  into X with range of cardinality k. This proves the identity when x is a positive integer. But this means that if we consider x as a variable the polynomials on the two sides have infinitely many values in common. Therefore, they must be identical.

Solution (b):

Again, we may assume that x is a positive integer. If a permutation \pi of a set S has exactly k cycles, then

x^{k}, then x^{k} is the number of x-colorations of S invariant under \pi. The left hand side of the identity sums these numbers for all permutations \pi of S=\{ 1 \ldots n \}. A given x-coloration of S is counted k_{1}!\ldots k_{x}! times, where k_{i} is the number of elements with color i. The number of occurrences of a given sequence k_{1},\ldots, k_{x} is

\frac{n!}{k_{1}!\ldots k_{x}!} and so, (fill this missing gap in proof) this sum is

\sum_{(k_{1},\ldots,k_{x}>0) (k_{1}+\ldots+k_{x}=n)}\frac{n!}{k_{1}!\ldots k_{x}!}k_{1}!\ldots k_{x}!

which equals

n! {{x+n-1}\choose n}=x(x+1)\ldots (x+n-1)

Solution (c):

Homework and do send comments, suggestions, questions…

More later,

Nalin Pithwa



Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.