**Prove the following identity (a):**

**Prove the following identity (b):**

**Prove the following identity (c);**

, if 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 where is a permutation of an n-element set S, and is a coloration of S with x colors invariant under .

**Hint (c):**

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

**Solution (a):**

Suppose first that x is a positive integer. Let and . The number of mappings of N into X is . 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 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 ways. Thus,

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 of a set S has exactly k cycles, then

, then is the number of x-colorations of S invariant under . The left hand side of the identity sums these numbers for all permutations of . A given x-coloration of S is counted times, where is the number of elements with color i. The number of occurrences of a given sequence is

and so, (*fill this missing gap in proof*) this sum is

which equals

**Solution (c):**

*Homework and do send comments, suggestions, questions…*

More later,

Nalin Pithwa