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