Throughout the problem, for every pair $( n , k )$ of strictly positive integers, we denote by $S ( n , k )$ the number of partitions of the set $\llbracket 1 , n \rrbracket$ into $k$ parts. We further set $S ( 0,0 ) = 1$ and, for all $( n , k ) \in \mathbb { N } ^ { * 2 } , S ( n , 0 ) = S ( 0 , k ) = 0$. Show that for all strictly positive integers $k$ and $n$, we have $$S ( n , k ) = S ( n - 1 , k - 1 ) + k S ( n - 1 , k )$$ One may distinguish the partitions of $\llbracket 1 , n \rrbracket$ according to whether or not they contain the singleton $\{ n \}$.
Throughout the problem, for every pair $( n , k )$ of strictly positive integers, we denote by $S ( n , k )$ the number of partitions of the set $\llbracket 1 , n \rrbracket$ into $k$ parts. We further set $S ( 0,0 ) = 1$ and, for all $( n , k ) \in \mathbb { N } ^ { * 2 } , S ( n , 0 ) = S ( 0 , k ) = 0$.
Show that for all strictly positive integers $k$ and $n$, we have
$$S ( n , k ) = S ( n - 1 , k - 1 ) + k S ( n - 1 , k )$$
One may distinguish the partitions of $\llbracket 1 , n \rrbracket$ according to whether or not they contain the singleton $\{ n \}$.