Given the set $N:=\{1,\cdots,n\}$, let $\pi$ be a permutation on $N$. We say $i \in \{1,\cdots,n\}$ is fixed by $g$ iff $\pi(i)=i.$

Denote the set of all permuations on $N$ by $S_n$. Define $f :~N \cup \{0\} \to \mathbb{N}_{\geq 0}$ by

$f(m):=$The number of permutations in $S_n$ which has exactly $m$ fixed points. Prove that $$\sum_{m=0}^{n} f(m) m^2=2n!$$

Remark: It seems $f(0)$ plays an prominent role.

  • $\begingroup$ It should be noted that the stated equality does not hold for $n=0$ and $n=1$. However for $n\geq2$ it is OK. $\endgroup$ – Marc van Leeuwen Oct 16 '12 at 8:39

This solution isn't fully combinatorial, but I think it works:

The sum we want is the number of permutations with an ordered pair $(i,j)$ such that the permutation is fixed at both $i$ and $j$. We can see this by noting that for a permutation with $m$ fixed points, we have $m^2$ choices of an ordered pair.

Now, to evaluate this number, we first choose an ordered pair. If $i \ne j$, there are $n^2-n$ choices of ordered pair and $(n-2)!$ choices of permutations. If $i = j$, there are $n$ choices of ordered pair and $(n-1)!$ choices of permutation, giving us a final answer of $(n^2-n)(n-2)! + n(n-1)! = 2n!.$

| cite | improve this answer | |
  • $\begingroup$ That is really nice! $\endgroup$ – MJD Oct 14 '12 at 4:52
  • $\begingroup$ A nice double counting trick! You counted the number of composite pairs $[(i,j),P]$ such that $P$ fixes $i$ and $j$. $\endgroup$ – user31899 Oct 14 '12 at 7:56
  • 3
    $\begingroup$ I don't know why you say this isn't fully combinatorial; I couldn't imagine anything more combinatorial than this. Note that in passing you have shown the following surprising fact: if one selects a permutation and an ordered set of two of its fixed points, uniformly at random along all distinct possibilities, then the two fixed points are just as likely to be equal as to be distinct (both account for $n!$ possibilities). $\endgroup$ – Marc van Leeuwen Oct 15 '12 at 9:00
  • 1
    $\begingroup$ Great solution, +1; but the formulation "the number of permutations with an ordered pair $(i,j)$ such that the permutation is fixed at both $i$ and $j$" seems a bit misleading -- we want the number of pairs of ordered pairs and permutations with that property. To my mind the clearest way to exhibit your argument would be to write $$ \begin{align} \sum_{m=0}^nf(m)m^2&=\sum_\pi\sum_{i,j\text{ fixed by }\pi}1\\&=\sum_{i,j}\sum_{\pi\text{ fixes }i,j}1\\&=\sum_i\sum_{\pi\text{ fixes }i}1+\sum_{i\ne j}\sum_{\pi\text{ fixes }i,j}1\\&=\sum_i(n-1)!+\sum_{i\ne j}(n-2)!\\&=n!+n!\\&=2n!\;. \end{align} $$ $\endgroup$ – joriki Oct 21 '12 at 17:53

This is another question that can be addressed using the symbolic method, as seen here. While this is not necessarily the simplest solution it does produce explicit forms of all generating functions and makes the problem amenable to automatic combinatorics, a powerful method developed by Chyzak, Salvy and Flajolet.

Permutations are sets of cycles, having combinatorial class specification $\mathfrak P(\mathfrak C(\mathfrak Z))$. Hence the corresponding exponential generating function (EGF) is $$ \exp \log \frac{1}{1-z} = \frac{1}{1-z},$$ where $$ \log \frac{1}{1-z} $$ is the EGF of labelled cycles. (These two are easily verified as there are $n!$ permutations and $n!/n$ cycles.)

If we want to count the number of fixed points we need to mark each fixed point with a new variable, $u$, which gives the class specification $\mathfrak P(\mathfrak C(\mathcal Z) -\mathcal Z + \mathcal U \mathcal Z )$. and the mixed generating function $$G(z, u) = \exp \left( \log \frac{1}{1-z} -z + uz \right) = \frac{1}{1-z} e^{-z} e^{uz}. $$

A term $u^m z^n/n!$ in $G(z, u)$ represents a permutation of length $n$ with $m$ fixed points. We seek to multiply this term by $m^2$. Hence we differentiate with respect to $u$, multiply by $u$, differentiate by $u$ again and finally multiply by $u$ one more time, obtaining $$ H(z, u) = \frac{1}{1-u} u \left( \frac{d}{du} \left( u \frac{d}{du} G(z, u) \right)\right) = \frac{1}{1-u} \frac{1}{1-z} e^{-z} (uz + u^2z^2) e^{uz}.$$ The factor $\frac{1}{1-u}$, when it occurs in a product with another formal power series in $u$, will produce the series for the sums of the first $n$ elements. It is included here to build a generating function for the sum, so that $$ n! [u^n][z^n] H(z, u) = \sum_{m=0}^n f(m, n) m^2.$$

The differentiate-and-multiply is known as a so-called marking operation in symbolic combinatorics.

It remains to extract coefficients. We have $$ \begin{align} & [z^n] \frac{1}{1-u} \frac{1}{1-z} e^{-z} \, uz \, e^{uz} = \frac{u}{1-u} [z^{n-1}] \frac{1}{1-z} e^{(u-1)z} \\ &= \frac{u}{1-u} \sum_{k=0}^{n-1} [z^k] e^{(u-1)z} = \frac{u}{1-u} \sum_{k=0}^{n-1} \frac{(u-1)^k}{k!} \\ &= u \left( \frac{1}{1-u} - \sum_{k=1}^{n-1} \frac{(u-1)^{k-1}}{k!}\right) \end{align}$$ Similarly, $$ \begin{align} & [z^n] \frac{1}{1-u} \frac{1}{1-z} e^{-z} \, u^2z^2 \, e^{uz} = \frac{u^2}{1-u} [z^{n-2}] \frac{1}{1-z} e^{(u-1)z} \\ &= \frac{u^2}{1-u} \sum_{k=0}^{n-2} [z^k] e^{(u-1)z} = \frac{u^2}{1-u} \sum_{k=0}^{n-2} \frac{(u-1)^k}{k!} \\ &= u^2 \left( \frac{1}{1-u} - \sum_{k=1}^{n-2} \frac{(u-1)^{k-1}}{k!}\right) \end{align}$$

It follows that $$ n! H(z, u) = n! [u^n] \left( u \left( \frac{1}{1-u} - \sum_{k=1}^{n-1} \frac{(u-1)^{k-1}}{k!} \right) + u^2 \left( \frac{1}{1-u} - \sum_{k=1}^{n-2} \frac{(u-1)^{k-1}}{k!}\right)\right)$$ which yields $$n! \, [u^n] \left( u \frac{1}{1-u} + u^2 \frac{1}{1-u} \right)= 2n!,$$ which was to be shown.

The beauty of this method is that it is algorithmic and can be implemented in computer algebra systems as in the package mentioned above. It is actually possible to have a program calculate all the generating functions that we have seen using only the specification of the combinatorial class.

There is much more on this method at Wikipedia.

| cite | improve this answer | |

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.