Where am I misunderstanding this formula for Stirling numbers

63 Views Asked by At

Wkipedia says to count surjections with inclusion exclusion for this formula for the stirling numbers:$${n\brace k}={\frac {1}{k!}}\sum _{{j=0}}^{{k}}(-1)^{{k-j}}{k \choose j}j^{n}$$ I get that for $j=k, k^n$ counts the number of ways to put n balls into k possibly empty boxes and we need to subtract the ways that end up putting balls into empty boxes. The next term, ${k\choose1}(k-1)^n$ removes the cases where there are 1 empty boxes, but removes too many when there are 2 or more empty boxes: it removes $k{k-1 \choose 1}(k-2)^n$ when originally there were only ${k\choose 2} (k-2)^n$ ways to have 2 or more empty boxes. So we add back ${k\choose 2}(k-2)^n$, but like before, we add back too many of when there are 3 or more empty boxes: ${k \choose 2}{k-2 \choose 1}(k-3)^n =3{k \choose 3}(k-3)^n$, so we should remove that many on the next term, but the next term only removes ${k\choose 3}(k-3)^n$ after which I knew I went wrong somewhere (The formula only removes back ${k\choose3} (k-3)^n$? Maybe I'm forgetting to count the cases where 3 or more boxes are empty during the previous add and removes but I haven't succeeded by accounting for those either. (0th term overcounts by ${k\choose3}(k-3)^n$,first term removes $k{k-1 \choose 2}(k-3)^n$, second term adds back as above, it doesn't add up)