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