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!