Problem

Source: III International Festival of Young Mathematicians Sozopol 2012, Theme for 10-12 grade

Tags: combinatorics, set theory



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