# Computing $S(n,3)$, Stirling number of 2nd kind

To compute this I used the fact that $$S(n,2) = 2^{n-1}-1$$ and used the recurrence relation $$S(n,k) = kS(n-1,k) + S(n-1,k-1)$$, and used induction to get that $$S(n,3)=\dfrac{3^{n-1}+1}{2}-2^{n-1}$$.

But is there a quicker way to do this? Is there a way to just see plainly, as in, just counting how many ways we could put $$n$$ distinguishable balls into $$3$$ indistinguishable boxes where no box is empty? I tried but it seems difficult.

• $6S(n,3)$ is the number of surjections $\{1,\ldots,n\}\to\{1,2,3\}$ and these can be counted by inclusion-exclusion. – Lord Shark the Unknown Mar 2 at 13:08

With Stirling numbers of the second kind we have the combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}_{=k}(\textsc{SET}_{\ge 1}(\mathcal{Z})).$$

This yields the EGF

$$\frac{(\exp(z)-1)^k}{k!}.$$

Setting $$k=3$$ we find

$${n\brace 3} = n! [z^n] \frac{1}{6} (\exp(z)-1)^3.$$

Extracting the coefficient with $$n\ge 1$$ we have

$$\frac{1}{6} n! [z^n] (\exp(3z)-3\exp(2z)+3\exp(z)-1) \\ = \frac{1}{6} n! \left(\frac{3^n}{n!} - 3 \frac{2^n}{n!} + 3 \frac{1}{n!} \right) \\ = \frac{1}{6} (3^n - 3 \times 2^n + 3).$$

This is the claim.

• Nice. But what about finding $S(n,3)$ without generating functions using simple methods? – Wesley Mar 2 at 16:12
• As was remarked in the comments these can be computed by inclusion-exclusion. Use PIE to prove the binomial convolution formula, then set $k=3$, or fix $k$ before you apply PIE. (This proof has appeared several times at MSE.) – Marko Riedel Mar 2 at 16:33

$$3^{n-1}$$ counts ternary sequences of length $$n-1$$, symbols in $$\{0,1,2\}.$$

$$(3^{n-1}+1)/2$$ counts ternary sequences whose first nonzero symbol is a $$1$$, because half of the nonzero sequences have their first nonzero symbol equal to $$1$$.

To translate such a sequence into a partition, scan the sequence from left to right.

• If symbol $$i$$ is a $$0$$, place $$i+1$$ in the same part as $$1$$.

• For the first $$i^*$$ that the $$(i^*)^{th}$$ symbol is a $$1$$, place $$i^*+1$$ in a new part.
For subsequent $$i$$ whose $$i^{th}$$ symbol is $$1$$, place $$i+1$$ in the same part as $$i^*+1$$.

• For the first $$i^{**}$$ that the $$(i^{**})^{th}$$ symbol is a $$2$$, place $$i^{**}+1$$ in a new part.
For subsequent $$i$$ whose $$i^{th}$$ symbol is $$2$$, place $$i+1$$ in the same part as $$i^{**}+1$$.

However, there is a small problem. If the ternary string only consists of $$0$$s and $$1$$s, then the resulting partition will only have $$2$$ parts. These strings must be subtracted.