Finding a recurrence relation in combinatorics. let $ S(n,k)$ be the number of options to divide $[n]$ to $k$ non-empty subsets.


*

*find $ S(n,1)$ and $ S(n,2)$.

*find recurrence relation for $ S(n,k)$.


Ok, so my attempt was:


*

*$S(n,1)=1$ , because there is only one option to divide any set to 1 subset.
and after writing down how many options in case of $ S(2,2)$,$ S(3,2)$,$ S(4,2)$, i think i figured out that its : $ S(n,2)= 2^{n-1}-1$, but i dont know exactly how to explain it.

*i figured maybe to divide to a singleton of ${n}$ and then $ S(n-1,k-1)$, and number of possiblities to pick $n$ is $n \choose 1 $ $ = n$.


but $ S(n,k)= S(n-1,k-1) + n$ doesn't work for me.
Any help would be appreciated, i'm interested in understanding how should I look at these kind of questions, i'm a mathematics undergrad.
 A: To divide the set $[n]$ into $k$ non-empty subsets, there are two cases:


*

*Element $n$ is alone.

*Element $n$ is not alone.


In the first case, we can divide first the set $[n-1]$ into $k$ non-empty subsets, and then put element $n$ in any of the $k$ sets. There are $ S(n-1,k) \times k$ ways of doing this.
In the second case, we can divide the set $[n-1]$ elements into $k-1$ non emtpy subsets, and then put element $n$ in the extra set.  There are $S(n-1,k-1)$
ways of doing this.
This gives the recurrence
$$S(n,k)=k \, S(n-1,k)+S(n-1,k-1)$$
These are the Stirling numbers of the second kind
(In all this reasoning, we are assuming that subsets are unlabelled, that is, that their order don't matter)
Update: regarding the particular case $S(n,2)=2^{n-1}+1$, you can check it from the recurrence, using induction.
$$ S(n+1,2)=2 S(n,2)+1= 2 (2^{n-1}-1)+1= 2^n-1$$
or from the explicit formula, or from a simple combinatorial argument: to divide $n$ objects into two sets, you can do it in $2^n/2$ ways. To this you must substract the prohibited case (all elements in one set), so you get $2^{n-1}-1$
