Our professor gave us the theorem:
$S(n+1,m+1)=\sum\limits_{k=m}^n \binom{n}{k} S(k,m)$,
where $S(n,m)$ denotes the number of partitionings of a set with $n$ elements into $m$ blocks.
I don't want a proof of this equation as Wikipedia and our professor gave it to us. I just don't understand the intuition behind it.
Could someone explain using for example gifts and packages ?
On
Let show an example so you can visualize this. Let the set defined as $A:=\{a,b,c\}$, then the set $A$ have $3$ elements. The number of ways to make a partition of $A$ in two subsets is $3$, that is
$$\{\{a,b\},\{c\}\},\quad\{\{a,c\},\{b\}\},\quad\text{and}\quad\{\{b,c\},\{a\}\}$$
then $S(3,2)=3$.
The real key is that $\binom{n}{k}=\binom{n}{n-k}$. So you take $n+1$ gifts labeled $\{1,\dots n+1\}.$ Take gift $n+1$ and $n-k$ other gifts, and put them in the first package, then partition the remaining $k$ gifts into $m$ packages.