0
$\begingroup$

Let $p_{n}(k)$ denote the number of permutations of length $n$ with exactly $k$ fixed points (a fixed point of $\pi$ is an element $t$ such that $\pi(t)=t$ ). Show that the generating function $$ f_{n}(x)=\sum_{i=0}^{n} x^{i} p_{n}(i) $$ satisfies $f_{n}(1)=f_{n}^{\prime}(1)=n !$

EDIT: Question context: Math graduate course - Probabilistic methods (2020)
My work: since every permutation of length n has a number of fixed points between 0 and n included it implies that $f_{n}(1)=n !$

$\endgroup$
4
  • 1
    $\begingroup$ Have you got any thoughts of your own on this? Hint: $p_n(0)+p_n(1)$ is the number of permutations in $S_n$ with zero or with one fixed point. What can you say about $p_n(0)+p_n(1)+p_n(2)+\dots+p_n(n)$? How many fixed points are possible for permutations in $S_n$? $\endgroup$
    – JMoravitz
    Aug 3 at 21:26
  • $\begingroup$ Well I understand that the hint solves the first question, because every permutation of length n has a number of fixed points between 0 and n included. For the second part about the derivative I am not sure. After calculating I get $f_{n}^{\prime}(1)= \sum_{i=0}^{n} i p_{n}(i) $ but nothing after this. $\endgroup$ Aug 3 at 21:37
  • $\begingroup$ Note that the number of permutations of length $n$ with exactly $k$ fixed points is $\binom{n}{k}\mathcal{D}(n-k)$ because there are $\binom{n}{k}$ ways to choose the fixed points and $\mathcal{D}(n-k)$ to arrange the others, where $\mathcal{D}(k)$ is the number of Derangements of $k$ items. $\endgroup$
    – robjohn
    Aug 4 at 7:08
  • $\begingroup$ Context added following the guidelines. $\endgroup$ Aug 4 at 19:01
2
$\begingroup$

Note that the number of permutations of length $n$ with exactly $k$ fixed points is $\binom{n}{k}\mathcal{D}(n-k)$ because there are $\binom{n}{k}$ ways to choose the fixed points and $\mathcal{D}(n-k)$ to arrange the others, where $\mathcal{D}(k)$ is the number of Derangements of $k$ items.

Therefore, the generating function is $$ \begin{align} \overbrace{\sum_{k=0}^n\binom{n}{k}\mathcal{D}(n-k)x^k}^{f_n(x)} &=\sum_{k=0}^n\overbrace{\frac{n!}{k!(n-k)!}\vphantom{\sum_0^k}}^{\binom{n}{k}}\overbrace{\sum_{j=0}^{n-k}(-1)^j\frac{(n-k)!}{j!}}^{\mathcal{D}(n-k)}x^k\tag{1a}\\[6pt] &=n!\!\!\sum_{\substack{j,k\ge0\\j+k\le n}}\!\!\frac{(-1)^j}{j!\,k!}x^k\tag{1b}\\ &=n!\sum_{m=0}^n\sum_{j=0}^m\frac{(-1)^j}{j!\,(m-j)!}x^{m-j}\tag{1c}\\[3pt] &=n!\sum_{m=0}^n\frac1{m!}\sum_{j=0}^m\binom{m}{j}x^{m-j}(-1)^j\tag{1d}\\[3pt] &=\sum_{m=0}^n\frac{n!}{m!}(x-1)^m\tag{1e} \end{align} $$ Explanation:
$\text{(1a)}$: expand $\mathcal{D}(n-k)$ (from $(5)$ in this answer) and $\binom{n}{k}$
$\text{(1b)}$: cancel terms and reindex
$\text{(1c)}$: substitute $m=j+k$
$\text{(1d)}$: multiply and divide by $m!$
$\text{(1e)}$: apply the Binomial Theorem

Thus, for $0\le m\le n$, $$ f^{(m)}(1)=n!\tag2 $$

$\endgroup$
2
$\begingroup$

Consider permutations of $[n]$: Each permuatution will have $i$ fixed points (where $i $ ranges from $0$ to $n$) & for a given value $i$, $p_n(i)$ of them will have $i$ fixed points, so \begin{eqnarray*} p_n(0)+p_n(1) +\cdots+p(_n(n)=n! \end{eqnarray*} and thus $f_{n}(1)=n !$.

To show the second part we need to notice that $ip_n(i)=np_{n-1}(i-1)$. This can be shown by the following combinatorial arguement: Given a permuatation of $[n]$ with $i$ fixed points, choose one of these fixed points. Now delete this element and reorder the other larger elements by decreasing them by $1$ to give a permutation of $n-1$ with $i-1$ fixed points & each of these permutations can be obtained in $n$ possible ways.

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