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.