24
$\begingroup$

I came across this result while doing some representation theory of the permutation group $S_n$ $$ \sum\limits_{\sigma \in S_n} (\mbox{number of fixed points of } \sigma)^2 = 2 n!$$

This can be proved very easily using the permutation representation of $S_n$. Does anyone know of a direct, more elementary way of proving this without using any representation theory?

$\endgroup$
  • $\begingroup$ For reference, here is the rep theory proof: let $\chi$ be the character of the standard representation of $S_n$ by permutation matrices. Since the trace of a permutation matrix is the number of fixed points, $\langle \chi, \chi \rangle$ is the sum of the squares of the number of fixed points divided by $n!$. But it is standard that this rep is the sum of two distinct irreps, hence the inner product is $2$. $\endgroup$ – Aaron May 7 '14 at 22:45
20
$\begingroup$

You can use Burnside's lemma. $\text{Fix}(\pi)^2$ is the number of elements fixed by $\pi$ acting on $[n]^2$, where $[n] = \{ 1, 2, ... n \}$, so Burnside's lemma tells you that

$$\frac{1}{n!} \sum_{\pi \in S_n} \text{Fix}(\pi)^2$$

is the number of orbits of $S_n$ acting on $[n]^2$. But there are, by inspection, two such orbits: the ordered pairs $(a, b)$ where $a \neq b$, and the ordered pairs $(a, a)$.

(Exercise: generalize this argument to figure out $\displaystyle \frac{1}{n!} \sum_{\pi \in S_n} \text{Fix}(\pi)^k$.)

$\endgroup$
  • $\begingroup$ Answer: $\mathrm{B}_k$. $\endgroup$ – robjohn May 7 '14 at 23:51
  • $\begingroup$ @rob: not quite, but close! $\endgroup$ – Qiaochu Yuan May 7 '14 at 23:51
  • $\begingroup$ Really? If I extend my answer, I believe that the Bell numbers pop out. Time for more thinking. $\endgroup$ – robjohn May 7 '14 at 23:57
  • 2
    $\begingroup$ @rob: again, not quite, but close. What you said is true as long as $k \le n$. $\endgroup$ – Qiaochu Yuan May 8 '14 at 0:22
  • 2
    $\begingroup$ Okay, since $\binom{n}{j}j!(n-j)!=n!$ only when $n\ge j$, and $0$ when $n\lt j$, it should be $$\sum_{j=0}^n\left\{k\atop j\right\}$$ which, as you say, is $\mathrm{B}_k$ when $n\ge k$. $\endgroup$ – robjohn May 8 '14 at 1:23
16
$\begingroup$

Here is an answer using Derangements. Purely combinatoric.

For any set of $k$ elements there are $\mathcal{D}(n-k)$ permutations that fix those $k$ elements and derange the others. There are $\binom{n}{k}$ ways to choose the $k$ elements. So the sum of the square of the number of fixed points is $$ \begin{align} \sum_{k=0}^nk^2\binom{n}{k}\mathcal{D}(n-k) &=\sum_{k=0}^nk(k-1)\binom{n}{k}\mathcal{D}(n-k)\\ &+\sum_{k=0}^nk\binom{n}{k}\mathcal{D}(n-k)\\ &=\sum_{k=0}^nn(n-1)\binom{n-2}{k-2}\mathcal{D}((n-2)-(k-2))\\ &+\sum_{k=0}^nn\binom{n-1}{k-1}\mathcal{D}((n-1)-(k-1))\\[6pt] &=n(n-1)(n-2)!\\[12pt] &+n(n-1)!\\[12pt] &=2n!\tag{1} \end{align} $$ for $n\ge2$. We've used formula $(2)$ from the cited answer: $$ n!=\sum_{k=0}^n\binom{n}{k}\mathcal{D}(n-k)\tag{2} $$ For $n=1$, $n(n-1)(n-2)!+n(n-1)!=1$ and for $n=0$, the sum is $0$.


Generalization

Qiaochu asked a question that I had actually thought about, but had missed a fine point: How does this generalize for summing other powers of the number of fixed points? For this, we will use Stirling Numbers of the Second Kind (whose defining equation is below in red) and equation $(2)$ above. $$ \newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}} \begin{align} \sum_{k=0}^n\color{#C00000}{k^p}\binom{n}{k}\mathcal{D}(n-k) &=\sum_{k=0}^n\color{#C00000}{\sum_{j=0}^p\stirtwo{p}{j}\binom{k}{j}j!}\binom{n}{k}\mathcal{D}(n-k)\\ &=\color{#00A000}{\sum_{k=0}^n}\sum_{j=0}^p\stirtwo{p}{j}\binom{n}{j}j!\color{#00A000}{\binom{n-j}{k-j}\mathcal{D}((n-j)-(k-j))}\\ &=\sum_{j=0}^p\stirtwo{p}{j}\binom{n}{j}j!\color{#00A000}{(n-j)!}\\ &=\sum_{j=0}^n\stirtwo{p}{j}n!\tag{3} \end{align} $$ For $n\ge p$, $(3)$ can be simplified to $$ \sum_{j=0}^n\stirtwo{p}{j}n!=\mathrm{B}_pn!\tag{4} $$ where $\mathrm{B}_p=\displaystyle\sum_{j=0}^p\stirtwo{p}{j}$ are the Bell Numbers.

$\endgroup$
  • $\begingroup$ In general instead of counting the number of set partitions we're counting the number of set partitions into at most $n$ parts. This is precisely what is counted by the count of orbits when you use Burnside's lemma. $\endgroup$ – Qiaochu Yuan May 8 '14 at 18:35
  • $\begingroup$ @QiaochuYuan: So we can count those orbits using $(3)$, which simplifies to $(4)$ when $n\ge p$. $\endgroup$ – robjohn May 8 '14 at 19:11
14
$\begingroup$

We can use basic probability theory. Take a random permutation. Let $X_i=1$ if $i$ is a fixed point of the permutation, and let $X_i=0$ otherwise. Then the number of fixed points is $X_1+\cdots+X_n$. Square. We get $$\sum_i X_i^2+\sum_{(i,j), i\ne j} X_iX_j.$$ Now by the linearity of expectation, $$E((X_1+\cdots +X_n)^2)=\sum_iE(X_i^2)+\sum_{(i,j), i\ne j}E(X_iX_j).\tag{1}$$ We have $\Pr(Xi=1)=\frac{1}{n}$ and $\Pr(X_iX_j=1)=\frac{1}{n(n-1)}$.

It follows that $E((X_1+\cdots+X_n)^2)=2$. For our sum, multiply by the number $n!$ of permutations.

Remark: Another instance of a mean proof.

$\endgroup$
  • $\begingroup$ Do we need to assume that the $X_i$ are independent? $\endgroup$ – robjohn May 7 '14 at 23:31
  • 2
    $\begingroup$ No, linearity of expectation holds always. That's what makes it so powerful. The $X_i$ here are definitely not independent. But that doesn't matter. $\endgroup$ – André Nicolas May 7 '14 at 23:35
  • $\begingroup$ Ah, I was worried about the $X_iX_j$ sum, but now that I think about it, we don't need to worry about the other points being fixed, just as we don't when using inclusion-exclusion. (+1) $\endgroup$ – robjohn May 7 '14 at 23:42
  • $\begingroup$ This proof is really deceptive. I thought I could just go ahead and find a nice formula for the general case where you replace 2 by k, but the work required is the same as finding the number of ways of partitioning k :P $\endgroup$ – apurv May 8 '14 at 1:40
  • 1
    $\begingroup$ You are welcome. The nice thing about computing expectation in this way is that it bypasses the sometimes very painful process of finding the detailed distribution. $\endgroup$ – André Nicolas May 8 '14 at 1:58
4
$\begingroup$

The labelled species $\mathcal{Q}$ of permutations with fixed points marked that we are working with here is $$\mathfrak{P}\left(\mathcal{UZ} + \mathfrak{C}_2(\mathcal{Z}) + \mathfrak{C}_3(\mathcal{Z}) + \mathfrak{C}_4(\mathcal{Z})+\cdots\right).$$

Therefore the bivariate generating function corresponding to $\mathcal{Q}$ is given by $$G(z, u) = \exp\left(uz-z+\log\frac{1}{1-z}\right) = \frac{e^{-z}}{1-z} e^{uz}.$$ We want to turn the terms having shape $q\times u^k z^n/n!$ into $q\times k^2 z^n/n!$, so differentiate with respect to $u$ to get $$\frac{d}{du} G(z,u) = \frac{e^{-z}}{1-z} z e^{uz}$$ and multiply by $u$ for $$\left(u\frac{d}{du}\right) G(z,u) = \frac{e^{-z}}{1-z} uz e^{uz}.$$ Differentiate with respect to $u$ one more time to get $$\frac{d}{du}\left(u\frac{d}{du}\right) G(z, u) =\frac{e^{-z}}{1-z} \left(z e^{uz} + uz^2 e^{uz}\right)$$ and finally put $u=1$ for the end result $$\left.\frac{d}{du}\left(u\frac{d}{du}\right) G(z, u) \right|_{u=1} = \frac{e^{-z}}{1-z} \left(z e^{z} + z^2 e^{z}\right) = \frac{z+z^2}{1-z}.$$ Now for $n\ge 2$ we have $$n! [z^n] \frac{z+z^2}{1-z}= 2\times n!,$$ done (the value at $n=1$ is correct also). The collection of proofs on this page and their diversity is remarkable. A closely related species is studied at this recent MSE link.

Addendum. Here is a proof of the generalization by @robjohn. Observe that $$\left.\left(\frac{d}{du}\right)^k G(z, u)\right|_{u=1}$$ is the generating function of the factorial moments of the RV $F$ representing the fixed points, e.g. $$\left.\left(\frac{d}{du}\right)^3 G(z, u)\right|_{u=1} = \sum_{n\ge 0} \mathrm{E}[F_n(F_n-1)(F_n-2)] z^n.$$ Now recall that $$x^q = \sum_{k=0}^q {q\brace k} x^{\underline{k}}.$$ This immediately implies that $$\mathrm{E}[F_n^q] = [z^n] \sum_{k=0}^q {q\brace k} \left.\left(\frac{d}{du}\right)^k G(z, u)\right|_{u=1} = [z^n] \sum_{k=0}^q {q\brace k}\left. \frac{e^{-z}}{1-z} z^k e^{uz}\right|_{u=1} \\ = [z^n] \sum_{k=0}^q {q\brace k} \frac{z^k}{1-z}.$$ This means that for $n\ge q$ we have $$\mathrm{E}[F_n^q] = \sum_{k=0}^q {q\brace k} = B_q$$ as claimed.

$\endgroup$
  • $\begingroup$ +1 I have a hard time understanding this answer because I know nothing about analytic combinatorics and species theory. After I follow the links in the your another answer, I finally have a grasp of what it mean. It is indeed a very powerful methodology. I think you should start your answer with a link to the external references so that people new to this methodology can follow the notation/logic in your answer more easily. $\endgroup$ – achille hui May 8 '14 at 2:43
  • $\begingroup$ The generating function used here can be read off from a use of Polya's enumeration theorem to give the generating function of the cycle index polynomials of the symmetric groups; see qchu.wordpress.com/2009/06/21/… and qchu.wordpress.com/2009/06/24/… for some details. Many combinatorial results about counting permutations based on or weighted by some property of their cycle decompositions can be immediately deduced. $\endgroup$ – Qiaochu Yuan May 8 '14 at 18:36
  • $\begingroup$ I agree. There is a list of such combinatorial results at Wikipedia -- Random Permutation Statistics. Actually when working with labelled species you only need the cardinality of the group (first term of cycle index usually), as opposed to unlabelled species, where the complete cycle index is used. There is a list of PET computations at MSE Meta. $\endgroup$ – Marko Riedel May 8 '14 at 18:51

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.