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

Basic Enumeration continued

Problem (a): Find recurrence relations for the Stirling partition numbers

$\left \{ \begin{array}{c} n \\ k \end{array} \right \}$ and the Stirling cycle numbers

$\left [ \begin{array}{c} n \\ k \end{array} \right ]$ and tabulate them for $n \leq 6$.

Problem (b): Prove that

$\left \{ \begin{array}{c} n \\ n-k \end{array} \right \}$ and

$\left [ \begin{array}{c} n \\ n-k \end{array} \right ]$ are polynomials in n for each fixed k.

Problem (c): Show that there is a unique way to extend the definition of

$\left \{ \begin{array}{c} n \\ k \end{array} \right \}$ and

$\left [ \begin{array}{c} n \\ k \end{array} \right ]$ over all integers n and k so that the recurrence relations in (a) are preserved and the “boundary conditions”

$\left \{ \begin{array}{c} 0 \\ 0 \end{array} \right \}$ which equals

$\left [ \begin{array}{c} 0 \\ 0 \end{array} \right ]=1$

and $\left \{ \begin{array}{c} 0 \\ m \end{array} \right \}$ which equals

$\left [ \begin{array}{c} m \\ 0 \end{array} \right ]=0$ ($m \neq 0$) are fulfilled.

Problem (d):

Prove the duality relation:

$\left \{ \begin{array}{c} n \\ k \end{array} \right \}$ is equal to

$\left [ \begin{array}{c} -k \\ -n \end{array} \right ]$.

Hints:

Hint (a):

Possible recurrence relations are

$\left \{ \begin{array}{c} n + 1 \\ k \end{array} \right \}$ which is equal to the sum of

$\left \{ \begin{array}{c} n \\ k -1 \end{array} \right \}$ and

$k \left \{ \begin{array}{c} n \\ k \end{array} \right \}$.

Hint (b):

Observe that in a partition of n elements into $n-k$ classes, at least $n-2k$ classes must be singletons.

Hint (c):

For the Stirling partition numbers, write the recurrence relations in (a) as

$\left \{ \begin{array}{c} n\\ k-1\end{array} \right \}$ is equal to the sum of

$\left \{ \begin{array}{c} n+1\\ k \end{array} \right \}$ and

$-k \left \{ \begin{array}{c} n \\ k \end{array} \right \}$ to get a recurrence for negative values of k.

Hint (d):

$\left \{ \begin{array}{c} n\\ k\end{array} \right \}$ and

$\left [ \begin{array}{c} -k\\ -n\end{array} \right ]$ satisfy the same recurrence and boundary conditions.

More later,

Nalin Pithwa.