The n-Category Café

Maybe some of you can help me understand (and thereby prove) Equations 5 and 6 in Arratia and Tavare’s paper. They cite another paper for this equation, from a journal on population biology! But I think it should be easy and fun to figure out ourselves.

These equations concern the random variable $C_k$ that I was discussing: the number of cycles of length $k$ in a random permutation of an $n$-element set. It’s a formula for expected values of products of such random variables.

We take a list of numbers $m_1 , \dots, m_\ell$ and compute the expected value of the random variable

$$C_1^{\underline{m}_1} \cdots C_\ell^{\underline{m}_\ell}$$

where the underline indicates ‘falling powers’:

$$x^\underline{m} = x(x-1)(x-2) \cdots (x-m+1)$$

Equation 5 says that

$$E(C_1^{\underline{m}_1} \cdots C_\ell^{\underline{m}_\ell} = \prod_{k = 1}^\ell \left( \frac{1}{k} \right)^{m_k}$$

or in other words

$$E\left( \prod_{k = 1}^\ell C_k^{\underline{m}_k} \right) = \prod_{k = 1}^\ell \left( \frac{1}{k} \right)^{m_k}$$

if $m_1 + 2 m_2 + \cdots + \ell m_\ell \le n$. It also says that if this inequality is violated, the expected value is $0$. So, the main thing I need to understand is this equation.

But then, in Equation 6, they reformulate this equation very suggestively as follows, given that the inequality holds:

$$E\left( \prod_{k = 1}^\ell C_k^{\underline{m}_k} \right) = E\left(\prod_{k = 1}^\ell Z_k^{\underline{m}_k}\right)$$

where the $Z_k$ are independent Poisson distributions with means $1/k$. To see why this reformulation works, I just need to see why

$$E\left(Z_k^{\underline{n}}\right) = \left( \frac{1}{k} \right)^{n}$$

This must be a famous thing about Poisson distributions. I think I’ve even used it before in my own work. I bet one proof uses Dobiński’s formula for the number of partitions of an $n$-element set. If we go this route, I’ll probably need to use the relation between partitions and permutations to figure out what’s really going on here.

Here are a bunch of facts I want to understand and somehow ‘unify’. My goal is to understand how permutations, partitions and the Poisson distribution are connected. These are some tidbits that seem to hint at a deep connection.

1) Let $P$ be the Poisson distribution of mean $1$. Then the $n$th moment of $P$ is the number of partitions of an $n$-element set. In other words:

$$E[P^n] = \sum_{k=0}^n S(n,k)$$

where $S(n,k)$ is the number of partitions of $n$ into $k$ parts. This is sometimes called Dobiński’s formula.

More generally let $P(x)$ be the Poisson distribution of mean $x$. Then

$$E[P(x)^n] = \sum_{k=0}^n S(n,k) x^k$$

I don’t really understand these facts. I know how to relate Gaussian integrals to combinatorics using Feynman diagrams. Something similar should be going on here: there should be some nice way to see why moments of a Poisson distribution are governed by partitions of $n$ into $k$ parts. I know that Poisson distributions can be seen as the Fock space description of coherent states, so I have hopes.

2) Consider the falling power

$$x^\underline{n} = x(x-1)(x-2) \cdots (x-n+1)$$

which is the number of injections $n \hookrightarrow x$ when $x$ is an integer. It obeys a formula like this:

$$x^n = \sum_{k=0}^n S(n,k) x^{\underline k}$$

where $S(n,k)$ is the number of partitions of $n$ into $k$ parts.

It’s enough to prove this equation for natural numbers since polynomials are equal if they agree on all natural numbers. If $x$ is a natural number we can prove the equation as follows.

Interpret $x$ as a finite set and $x^n$ as the set of functions $n \to x$. Any such function has an epi-mono factorization which is unique up to isomorphism. That is, it’s given by some surjection $n \to k$, which gives a partition of $k$ into $n$ parts, followed by an injection $k \hookrightarrow n$. If we count the number of options (paying careful attention to avoid overcounting) we get the right side of the above equation.

This argument goes back to Rota.

3) Putting 1) and 2) together we get

$$E[P^{\underline{n}}] = 1$$

Conversely, this and 2) imply 1). Wikipedia’s proof of 1) reduces it to proving $E[P^{\underline{n}}] = 1$ in this way, and then quits there. This is not entirely satisfying!

4) On the other hand,

$$x^\underline{n} = \sum_{k=0}^n s(n,k) x^k$$

where $s_{n,k}$ is $(-1)^{n-k}$ times the number of permutations of $n$ with exactly $k$ disjoint cycles. This is a kind of ‘inverse transform’, reversing the change of basis from polynomials $x^{\underline k}$ to polynomials $x^n$ given in 2). But what’s really going on here, combinatorially?