Simplify $\sum_{i,j}\left[{n}\atop{i+j}\right]\binom{i+j}{i}$ I have to simplify $\sum_{i,j}\left[{n}\atop{i+j}\right]\binom{i+j}{i}$. I looks like we have $n$ children and we have to answer how many times we can arrange them into circles and color some of circles red.
 A: We can make use of the identities
$$\sum_{k=m}^n{n\brack k}\binom{k}m={{n+1}\brack{m+1}}$$
and
$$\sum_{k=0}^n{n\brack k}=n!$$
to get
$$\begin{align*}
\sum_{i=0}^n\sum_{j=0}^{n-i}{n\brack{i+j}}\binom{i+j}i&=\sum_{k=0}^n\sum_{i=0}^k{n\brack k}\binom{k}i\\
&=\sum_{i=0}^n\sum_{k=i}^n{n\brack k}\binom{k}i\\
&=\sum_{i=0}^n{{n+1}\brack{i+1}}\\
&=\sum_{i=1}^{n+1}{{n+1}\brack i}\\
&=(n+1)!\;.
\end{align*}$$
At the first step $k=i+j$.
A: We have:
$${n \brack k}=[x^k]\left(x\cdot(x+1)\cdots(x+k-1)\right) = [x^k](x)^{(n)}\tag{1} $$
and:
$$ \binom{k}{i} = [x^k]\frac{x^i}{(1-x)^{i+1}}=[x^{-k}]\frac{x}{(x-1)^{i+1}}\tag{2} $$
so for a fixed $i$ we have:
$$\sum_{k}{n\brack k}\binom{k}{i} = \text{Res}\left(\frac{(x)^{(n)}}{x^n(x-1)^{i+1}},x=0\right)={n+1\brack i+1}\tag{3}$$
and by summing the RHS of $(3)$ over $i$ we simply get:
$$\sum_{i,k}{n\brack k}\binom{k}{i}= \sum_i {n+1\brack i+1} = \left.(x)^{(n+1)}\right|_{x=1}=\color{red}{(n+1)!}.\tag{4}$$
A: Starting from the usual basics recall that the species of permutations
in terms of cycles is given by
$$\mathcal{P} = \mathfrak{P}(\mathfrak{C}(\mathcal{Z}))$$
which implies  that the bivariate generating  function of permutations
by cycles is $$G(z, u) = \exp\left(u \log\frac{1}{1-z}\right).$$
This implies that
$$\left[n\atop k\right] =
n![z^n] [u^k] \exp\left(u \log\frac{1}{1-z}\right).$$
We obtain for the sum
$$\sum_{p=0}^n \sum_{q=0}^{n-p} 
\left[n\atop p+q\right] {p+q\choose q}
\\ = n! [z^n] \sum_{p=0}^n \sum_{q=0}^{n-p}
{p+q\choose q} \frac{1}{(p+q)!}
\left(\log\frac{1}{1-z}\right)^{p+q}
\\ = n! [z^n] 
\sum_{p=0}^n \frac{1}{p!} \left(\log\frac{1}{1-z}\right)^{p}
\sum_{q=0}^{n-p}
\frac{1}{q!} \left(\log\frac{1}{1-z}\right)^{q}.$$
Now  observe  carefully that  we  are  extracting  the coefficient  on
$[z^n]$ and  the two logarithmic  terms start at $[z^p]$  and $[z^q].$
Therefore  we may extend  the sum  in the  second logarithmic  term to
infinity because when $q\gt n-p$ we have $p+q \gt n.$
We get
$$n! [z^n] 
\sum_{p=0}^n \frac{1}{p!} \left(\log\frac{1}{1-z}\right)^{p}
\sum_{q\ge 0}
\frac{1}{q!} \left(\log\frac{1}{1-z}\right)^{q}
\\ = n! [z^n] 
\sum_{p=0}^n \frac{1}{p!} \left(\log\frac{1}{1-z}\right)^{p}
\exp\log\frac{1}{1-z}
\\ = n! [z^n] \frac{1}{1-z}
\sum_{p=0}^n \frac{1}{p!} \left(\log\frac{1}{1-z}\right)^{p}.$$
The  same  observation (no  contribution  to  $[z^n]$  when $p\gt  n$)
applies to the remaining logarithmic term and we get
$$ n! [z^n] \frac{1}{1-z} \exp\log\frac{1}{1-z}
= n! [z^n] \frac{1}{(1-z)^2}
\\ = n! \times {n+1\choose 1} = (n+1)!$$
as claimed.
