If $S(n, n - 3) = a \binom n 4 + b \binom n 5 + c \binom n 6$, find $a, b, c$ (where $S(n, k)$ denotes a Stirling number of the second kind)

Question

Given the identity $S(n, n - 3) = a \binom n 4 + b \binom n 5 + c \binom n 6$, find $a, b, c$. $S(n, k)$ denotes a Stirling number of the second kind, i.e., the number of ways to place $n$ labeled balls into $k$ non-labeled non-empty boxes.

My reasoning is the following: $S(n, n - 3)$ gives the number of ways to place $n$ labeled balls into $n - 3$ non-labeled non-empty boxes (as per the definition of $S(n, k)$). This can be accomplished under the following scenarios:

1. $3$ empty boxes, one of the non-empty boxes contains $4$ balls,
2. $3$ empty boxes, one of the non-empty boxes contains $3$ balls, another one contains $2$ balls,
3. $3$ empty boxes, three of the non-empty boxes contain $2$ balls each,

and all remaining boxes contain $1$ ball each. The binomial coefficients above correspond to the three given scenarios. In order to find $a, b, c$, we need to find in how many ways each scenario can occur. So:

1. The $4$ balls can be put in only $1$ way, giving $a = 1$;
2. The $5$ balls can be put in $\binom 5 3$ ways, giving $b = 10$;
3. The $6$ balls can be put in $\binom 6 2 \binom 4 2$ ways, giving $c = 90$.

However, it would seem that $c = 15$ and I'm overcounting. Can anyone spot the mistake (or perhaps I'm doing this completely wrong)?

Answer 1

The basic idea is fine, but the details for $c$ are not: you’re overcounting. What you want is the number of ways to divide $6$ objects into $3$ pairs. Temporarily number the objects $1$ through $6$. There are $5$ ways to choose a mate for object $1$. Once the pair containing object $1$ has been decided, there are $3$ ways to choose a mate for the smallest-numbered object remaining. And once that’s been done, all $3$ pairs have actually been determined, so the desired coefficient is $5\cdot3=15$.

There’s more discussion of counting ways to pair up objects at this question and its answers

Answer 2

For future reference because we are using an EGF which may not be admissible here. Recall that the species of set partitions is given by

$$\mathfrak{P}(\mathfrak{P}_{\ge 1}(\mathcal{Z})).$$

We seek to evaluate $${n\brace n-3}.$$

Now since these sets are not empty we must first put a labelled ball into each of the $n-3$ slots. This leaves three labeled balls. We can partition these as follows: $3$, $1+2$ and $1+1+1.$

The first case yields

$$\mathfrak{P}_{=4}(\mathcal{Z}) \mathfrak{P}_{=n-4}(\mathcal{Z}).$$

The second case yields

$$\mathfrak{P}_{=2}(\mathcal{Z})\mathfrak{P}_{=3}(\mathcal{Z}) \mathfrak{P}_{=n-5}(\mathcal{Z}).$$

The third case yields

$$\mathfrak{P}_{=3}(\mathfrak{P}_{=2}(\mathcal{Z})) \mathfrak{P}_{=n-6}(\mathcal{Z}).$$

The term involving $n$ represents the singleton sets. We thus get for the generating function

$$G(z) = \frac{z^4}{24}\frac{z^{n-4}}{(n-4)!} + \frac{z^2}{2}\frac{z^3}{6}\frac{z^{n-5}}{(n-5)!} + \frac{1}{6} \left(\frac{z^2}{2}\right)^3 \frac{z^{n-6}}{(n-6)!}.$$

Extracting coefficients from this yields

$$n! [z^n] G(z) = {n\choose 4} + 10 {n\choose 5} + 15 {n\choose 6}.$$

Addendum. We can treat the general case when we evaluate $${n\brace n-k}$$

in terms of binomial coefficients $${n\choose n-k-q} = {n\choose k+q}$$ where $1\le q\le k.$

Solving these for small $k$ points us to OEIS A269939 (Ward numbers) where we find the formula

$${n\brace n-k} = \sum_{q=1}^k {n\choose n-k-q} \sum_{m=0}^q {k+q\choose k+m} (-1)^{m+q} {k+m\brace m}$$

which we now prove.

Recalling the bivariate generating function for set partitions (Stirling numbers of the second kind) which is

$$G(z, u) = \exp(u(\exp(z)-1))$$

we get for the sum

$$\sum_{q=1}^k {n\choose n-k-q} \\ \times \sum_{m=0}^q \frac{(k+q)!}{(k+m)!(q-m)!} (-1)^{m+q} (k+m)! [z^{k+m}] \frac{(\exp(z)-1)^m}{m!} \\ = n! \sum_{q=1}^k \frac{1}{(n-k-q)!} \frac{1}{q!} \\ \times \sum_{m=0}^q {q\choose m} (-1)^{m+q} [z^{k+m}] (\exp(z)-1)^m \\ = \frac{n!}{(n-k)!} \sum_{q=1}^k {n-k\choose q} \sum_{m=0}^q {q\choose m} (-1)^{m+q} [z^{k+m}] (\exp(z)-1)^m.$$

Now introduce

$$[z^{k+m}] (\exp(z)-1)^m = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+m+1}} (\exp(z)-1)^m \; dz$$

to get for the inner sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \sum_{m=0}^q {q\choose m} (-1)^{q-m} \frac{(\exp(z)-1)^m}{z^m} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \left(\frac{\exp(z)-1}{z}-1\right)^q \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+q+1}} \left(\exp(z)-z-1\right)^q \; dz.$$

This yields for the outer sum

$$\frac{n!}{(n-k)!} \sum_{q=1}^k {n-k\choose q} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+q+1}} \left(\exp(z)-z-1\right)^q \; dz.$$

Now observe carefully that when $q\gt k$ then $2q\gt k+q$ and since $\exp(z)-z-1$ starts at $z^2/2$ and hence $(\exp(z)-z-1)^q$ at $z^{2q}/2^q$ the integral is zero in this case. Furthermore with $k\ge 1$ we also get zero from the integral when $q=0.$ Therefore we are justified in letting the sum range from zero to $n-k$ and we obtain

$$\frac{n!}{(n-k)!} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \sum_{q=0}^{n-k} {n-k\choose q} \frac{1}{z^q} \left(\exp(z)-z-1\right)^q \; dz \\ = \frac{n!}{(n-k)!} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \left(1 + \frac{\exp(z)-z-1}{z}\right)^{n-k} \; dz \\ = \frac{n!}{(n-k)!} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \left(\exp(z)-1\right)^{n-k} \; dz.$$

This is $$n! [z^n] \frac{(\exp(z)-1)^{n-k}}{(n-k)!} = {n\brace n-k}$$

and we are done.

Note that when $k\gt n-k$ we are also justified in lowering the upper limit of the sum to $n-k$ because the segment being omitted is zero due to the binomial coefficient ${n-k\choose q}.$

Alternate ending. We may use the formula for the outer sum to obtain a combinatorial expression. Start from

$$\frac{n!}{(n-k)!} \sum_{q=1}^k {n-k\choose q} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+q+1}} \left(\exp(z)-z-1\right)^q \; dz \\ = \sum_{q=1}^k \frac{n!}{(n-k-q)!} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+q+1}} \frac{\left(\exp(z)-z-1\right)^q}{q!} \; dz \\ = \sum_{q=1}^k {n\choose k+q} \frac{(k+q)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+q+1}} \frac{\left(\exp(z)-z-1\right)^q}{q!} \; dz \\ = \sum_{q=1}^k {n\choose k+q} {k+q\brace q}_{\ge 2}.$$

This is ${n\brace n-k}$ by inspection. Recall that we start by placing a labeled singleton in each of the $n-k$ slots. The remaining $k$ items are divided into $q$ sets where $1\le q\le k.$ Each of these joins a singleton, so in fact a configuration is completely determined by the elements that are in a set containing at least two elements. That's what the formula on the last line represents -- first choose the $k+q$ items for those sets and combine that choice with a partition of these items into $q$ sets of cardinality at least two. (We have $k+q$ items because the singletons from the beginning contribute $q$ of them.)

Remark. Having reached the end of this computation we see that the variable in the integral was never substituted and rested inert. That means we could have used the coefficient extractor notation throughout without affecting the semantics of the argument.