Prove combinatorial identity Prove the following identity:
$$
{{i+j}\choose{i}}\left\{{n}\atop{i+j}\right\} = \sum_{k=0}^n{{n}\choose{k}}\left\{{k}\atop{i}\right\}\left\{{n-k}\atop{j}\right\}
$$
 A: Suppose we are trying to prove that
$${n\brace p+q} {p+q\choose p}
= \sum_{k=0}^n {n\choose k} {k\brace p} {n-k\brace q}.$$
We  will use exponential  generating functions  in $n$.  The RHS  is a
convolution  of   two  generating  functions  call   them  $A(z)$  and
$B(z)$. The first is $$\sum_{m\ge 0} {m\brace p}\frac{z^m}{m!}.$$
Recall the  bivariate generating function  of the Stirling  numbers of
the second kind:
$$\exp(u(\exp(z)-1))$$
so that
$${n\brace k} = n! [z^n] [u^k] \exp(u(\exp(z)-1)). $$
This yields
$$A(z) = \sum_{m\ge 0} 
\frac{z^m}{m!}
m! [z^m] \frac{1}{p!} (\exp(z)-1)^p.$$
which is
$$\sum_{m\ge 0} 
z^m [z^m] \frac{1}{p!} (\exp(z)-1)^p.$$
The sum cancels the coefficient extractions and we get
$$A(z) = \frac{1}{p!} (\exp(z)-1)^p.$$
Similarly,
$$B(z) = \frac{1}{q!} (\exp(z)-1)^q.$$
Therefore 
$$A(z) B(z) = \frac{1}{(p+q)!} 
{p+q\choose p} (\exp(z)-1)^{p+q}.$$
The generating function of the LHS with respect to $n$ is
$${p+q\choose p} \frac{1}{(p+q)!} (\exp(z)-1)^{p+q}.$$
The two generating functions are the same, QED.
Observation. A combinatorial proof goes like this. The left counts
the number  of ways of  partitioning $n$ labelled elements  into $p+q$
sets and marking $p$ of these. This is the same as the right, where we
choose $k$ elements from the $n$  elements for the $p$ marked sets and
$n-k$ for the umarked ones.
This MSE link I illustrates the convolution technique, as does this
MSE link II.
Observation II. Instead of substituting the coefficients from the bivariate generating function to obtain $A(z)$ and $B(z)$ we could have argued from first principles that they represent the species $$\mathfrak{P}_p(\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ and $$\mathfrak{P}_q(\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ and obtained them by direct translation.
