Here is a simple but cute computation that makes a good exercise in elementary representation theory with a probabilistic flavor — as usual, it’s probably well-known, but I wasn’t aware of it until doing the exercise myself.
We consider random permutations in the symmetric group , and write
for the number of cycles in the disjoint cycle representation of
. It is a well-known fact (which may be due to Feller) that, viewed as a random variable on
(with uniform probability measure), there is a decomposition in law
where is a Bernoulli random variable taking value
with probability
and
with probability
, and moreover the
‘s are independent.
This decomposition is (in the sources I know) usually proved using the “Chinese Restaurant Process” to describe random permutations ( guests numbered from
to
enter a restaurant with circular tables; they successively sit either at the next available space of one of the tables already occupied, or pick a new one, with the same probability; after all
guests are seated, reading the cycles on the occupied tables gives a uniformly distributed element of
.) If one is only interested in
, then the decomposition above is equivalent to the formula
for the probability generating function of . (This formula comes up in mod-poisson convergence of
and in analogies with the Erdös-Kac Theorem, see this blog post).
Here is an algebraic proof of this generating function identity. First, is a polynomial, so it is enough to prove the formula when
is a non-negative integer. We can do this as follows: let
be a vector space of dimension
over
. Then define
and view it as a representation space of
where the symmetric group permutes the factors in the tensor product. Using the “obvious” basis of
, it is elementary that the character of this representation is the function
on
(the matrix representing the action of
is a permutation matrix). Hence, by character theory,
is the dimension of the
-invariant subspace of
. Since the representation is semisimple, this is the dimension of the coinvariant space, which is the
-th symmetric power of
This in turn is well-known (number of monomials of degree
in
variables), and we get
as claimed!