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) 
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:


*

*$3$ empty boxes, one of the non-empty boxes contains $4$ balls,

*$3$ empty boxes, one of the non-empty boxes contains $3$ balls, another one contains $2$ balls,

*$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:


*

*The $4$ balls can be put in only $1$ way, giving $a = 1$;

*The $5$ balls can be put in $\binom 5 3$ ways, giving $b = 10$;

*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)?
 A: 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
A: 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. 
