5
$\begingroup$

Let $X_N$ be the random variable corresponding to the number of fixed points (1-cycles) in a permutation chosen uniformly at random from $S_N$.

Then, the $m^{\text{th}}$ moment, when $m < N$, is equal to $B_m$ where $B_k$ is the $k^{\text{th}}$ Bell number (equal to the number of partitions of the set $[k]$).

This is a really interesting combinatorial fact, not least because all the moments are integers (moments past the $N^{\text{th}}$ are as well) and deserves a combinatorial solution.

Now, I have two proofs that are fairly combinatorial - however, both involve sums and avoid the combinatorial meaning of $X_{N}^m$, whatever that may be. I reproduce the first below:

Let $X_N$ be the number of fixed points in a random permutation on $N$ elements. It is well known that $E[X_N]=1$.

For $0\leq M \leq N$, $E\left[{X_N \choose M}\right]$ counts the expected number of sets of $M$ fixed points. We can count this using indicator random variables. Consider all subsets of $[N]$ containing $M$ elements.

The probability that a subset of size $M$ is pointwise fixed by a random permutation $\pi$ is $\frac{(N-M)!}{N!}$ because there are $(N-M)!$ permutations on the remaining elements that keep the subset of $M$ elemnts fixed (the number of automorphisms on $[N]-[M]$). This factor can also come from realizing that a permutation on $[N]$ induces an injection from a subset of $M$ elements to $[N]$ of which only $1$ sends each element to itself. Because the injections are uniformly chosen, we have a factor of $\frac{1}{N^{\underline{M}}} = \frac{(N-M)!}{N!}$.

Hence the expected value is ${N \choose M} \times \frac{(N-M)!}{N!} = \frac{1}{M!}$. Hence the expected value of $E[(X_N)^{\underline{M}}]$ is $1$.

Hence the expected value of $E[(X_N)^M]$ is $B_M$, the $M^{th}$ Bell Number for $0 \leq M \leq N$.

However, this involves at the end an ugly summation and (in my mind) fails to capture why the expectation ought to be an integer outside of coincidence.

It is also the case that as $N \rightarrow \infty$, $X_N \rightarrow \text{Poi}(1)$ where Poi($\lambda$) is the Poisson distribution with mean $\lambda$. Hence, it may be related to properties of the Poisson random distribution when the mean is $1$. I believe that the number of $k$-cycles is in generally asymptotically Poi($1/k$) but I don't remember where I read this and have not proven it myself - it would be interesting to see if they too had integer moments though I'd doubt it.

I'm really just looking for combinatorial intuition on this - a proof that doesn't involve summation or less intuitive things would be nice (summation in the context of a union is fine, but the random M! in the above summation leaves me unhappy). Thanks for your help!

$\endgroup$
  • $\begingroup$ Two papers in the American Mathematical Monthly are relevant: One by Gian-Carlo Rota published in 1964 titled The Number of Partitions of a Set and another one decades later by Jim Pitman. I've forgotten details of the latter. He shows that the first $N$ factorial moments (and hence the first $N$ moments) of the number of fixed points of a uniformly distributed random permutation are the same as those of the Poisson distribution with expected value $1$. $\qquad$ $\endgroup$ – Michael Hardy Jun 23 '16 at 21:53
3
$\begingroup$

The natural object for the $M$-th power of the number of fixed points isn't a subset of $M$ fixed points put an $M$-tuple of fixed points. Classify the $M$-tuples according to the subsets of entries that are equal. The number of these types is the Bell number $B_M$. A straightforward calculation shows that each such type contributes $1$ to the expected number of $M$-tuples of fixed points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.