# 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

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