# Number of permutations which fixes a certain number of point

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.

#### Solutions Collecting From Web of "Number of permutations which fixes a certain number of point"

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!.$

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.