1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Nice. But what about finding $S(n,3)$ without generating functions using simple methods? $\endgroup$ – Wesley Mar 2 at 16:12
  • $\begingroup$ 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.) $\endgroup$ – Marko Riedel Mar 2 at 16:33
0
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.