We denote with $p_n(k)$ the number of permutations of the numbers $1,2,...,n$ that have exactly $k$ fixed points. a) Prove that $\sum_{k=0}^n kp_n (k)=n!$. b) If $s$ is an arbitrary natural number, then: $\sum_{k=0}^n k^s p_n (k)=n!\sum_{i=1}^m R(s,i)$, where with $R(s,i)$ we denote the number of partitions of the set $\{1,2,...,s\}$ into $i$ non-empty non-intersecting subsets and $m=min(s,n)$.
Problem
Source: III International Festival of Young Mathematicians Sozopol 2012, Theme for 10-12 grade
Tags: combinatorics, set theory
enthusiast101
26.11.2019 17:40
$$\sum_{k=1}^{n}kp_n(k)$$$$=\sum_{k=1}^{n}k \binom{n}{k} D_{n-k}$$$$= \sum_{k=1}^{n} \left (k \frac{n!}{k!} (n-k)! \sum_{i=1}^{n-k} \frac{(-1)^{i+1}}{i!} \right)$$$$=\sum_{k=1}^{n} \frac{n! \sum_{i=1}^{n-k} \frac{(-1)^{i+1}}{i!}}{(k-1)!}$$$$=n! \sum_{k=1}^{n} \frac{1}{e(k-1)!}=\frac{n!}{e} \sum_{k=1}^{n} \frac{1}{(k-1)!}$$$$=n!$$
Letteer
01.12.2019 18:50
enthusiast101 wrote:
$$\sum_{k=1}^{n}kp_n(k)$$$$= \sum_{k=1}^{n}k \binom{n}{k} D_{n-k}$$$$= \sum_{k=1}^{n} \left(k \frac{n!}{k!} (n-k)! \sum_{i=1}^{n-k} \frac{(-1)^{i+1}}{i!} \right)$$$$ = \sum_{k=1}^{n} \frac{n! \sum_{i=1}^{n-k} \frac{(-1)^{i+1}}{i!}}{(k-1)!}$$$$=n! \sum_{k=1}^{n} \frac{1}{e(k-1)!}=\frac{n!}{e} \sum_{k=1}^{n} \frac{1}{(k-1)!}$$$$=n!$$
Your solution has several missteps. In your third equality, an $(n-k)!$ disappeared. Also, the equation $\sum_{i=1}^{n-k}\frac{(-1)^{i+1}}{i!}= e^{-1}$ used in your fourth equality is incorrect.
Here is a combinatorial solution. $\sum_{k=1}^nkp_k(n)$ counts the number of ordered pairs $(\pi,j)$, where $\pi$ is a permutation and $j$ is a fixed point of $\pi$. This is because there are $p_k(n)$ permutations with $k$ fixed points, and for each of those, there are $k$ choices for $j$.
To count the number of ordered pairs $(\pi,j)$, let us ask how many choices of $\pi$ there are for a given $j$. The number of permutations which have a given number $j$ as a fixed point is $(n-1)!$. Therefore,
$$\sum_{k=1}^nkp_k(n)$$=# of $(\pi,j)$ such that $j$ is fixed point of $\pi$
$=\sum_{j=1}^n$ # of $\pi$ such that $j$ is fixed point of $\pi$
$$=\sum_{j=1}^n (n-1)!$$$$= n\cdot (n-1)!=n!.$$
For $(b)$, you are instead counting ordered sequences $(\pi,j_1,j_2,\dots,j_s)$ so that $j_1,\dots,j_s$ are all fixed points of $\pi$, as there are $k^s$ ways to choose the list of $j_1,\dots,j_s$ when $\pi$ has $k$ fixed points. Given a list which contains $i$ distinct values, there are $(n-i)!$ ways to choose a permutation $\pi$ which has all those values as fixed points.
The number of lists $j_1,\dots,j_s$ which have exactly $i$ distinct values is $R(s,i)\cdot \frac{n!}{(n-i)!}.$ This is because such a list is formed by partitioning $\{1,2,\dots,s\}$ into $n$ parts, ordering the parts by smallest element, then assigning the first part one of $n$ numbers, then assigning the second one one of $(n-1)$ numbers different than the first, and so on.
Therefore,
$$ \sum_{k=1}^nk^sp_k(n)$$= # of $(\pi,j_1,\dots,j_s)$ such that each $j_i$ is fixed point of $\pi$
$= \sum_{i=1}^s$ (# $(j_1,\dots,j_s)$ $i$ distinct values) $\cdot$ (# of $\pi$ where $i$ particular points are fixed)
$$= \sum_{i=1}^s R(s,i)\cdot \frac{n!}{(n-i)!}\cdot (n-i)!$$$$= n! \sum_{i=1}^s R(s,i).$$