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!
If x is an integer, both sides of the first identity count mappings of an n element set into an x-element set.
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 .
Combine the identities in (a) and (b).
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.
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
Homework and do send comments, suggestions, questions…