Finite sum involving Stirling numbers

Question

I am trying to evaluate the following finite sum:

$$ \sum_{h=0}^{m}\binom{m}{h}2^{m-h}S(h,k-r)S(m-h,r),\qquad 0\leq r\leq k\leq m, $$

where $S(n,k)$ is the Stirling number of the second kind. Can you throw some light on it?

Thanks in advance.

Answer 1

This sum comes from the product of the exponential generating function of the Stirling numbers of the second kind with itself. The number of blocks in the first egf is $k-r$; the number of blocks in the other is $r$. The factor of $2^{m-h}$ can be accounted for by a factor of 2 in the variable of the second egf. Since the egf of the Stirling numbers of the second kind partitioned into $k$ blocks is $\frac{(e^x-1)^k}{k!}$, your sum is the coefficient of $x^m$ in $$\frac{(e^x-1)^{k-r}}{(k-r)!}\frac{(e^{2x}-1)^r}{r!}.$$ Algebraically, this simplifies to $\frac{(e^x-1)^k}{(k-r)!}\frac{(e^x+1)^r}{r!}$, which can be expanded with the binomial theorem to get a nice sum.

Edit:

Your sum is $[x^m]\frac{1}{r!(k-r)!}(e^x-1)^k (e^x+1)^r$ which, by the product formula, is $$\frac{1}{r!(k-r)!}\sum_{n=0}^m[x^n](e^x-1)^k\cdot [x^{m-n}](e^x+1)^r.$$ By the binomial theorem this is $$\frac{1}{r!(k-r)!}\sum_{n=0}^m\left(\sum_{\ell=0}^k\binom k\ell(-1)^{k-\ell}[x^n]e^{\ell x}\cdot\sum_{s=0}^r \binom rs[x^{m-n}]e^{sx}\right).$$ Extracting the coefficients, your sum is equivalent to $$\frac{1}{r!(k-r)!}\sum_{n=0}^m\left(\sum_{\ell=0}^k\binom k\ell(-1)^{k-\ell}\frac{\ell^n}{n!}\cdot\sum_{s=0}^r \binom rs\frac{s^{m-n}}{(m-n)!}\right).$$

Answer 2

By a combinatorial argument, perhaps it is also possible from the generating function you already have, you can arrive to the following recursion formula. $$A_{a,b,c}=cA_{a-1,b,c}+A_{a-1,b-1,c-1}+2(b-c)A_{a-1,b,c}+2A_{a-1,b-1,c},$$with initial values $A_{a,b,c}=0$ if $a<0$ or $b<0$ or $c<0$ or $a<b$ or $b<c$ and $A_{a,b,c}=\binom{b}{c}2^{b-c}$ if $a=b$.
The combinatorial argument is by counting the number of partitions$\lambda = \{B_i\}_{1\leq i\leq k}$ in the colored set $[a]$ with $3$ colors such that in each block $B_i$ if $x\in B_i$ and $x$ is colored with $0$ or $1$ then no element of $B_i$ is colored with color $2$. Also, the numbers of blocks in which each element is colored by $2$ is $c$.
Your formula counts the number of that kind of partitions by splitting in two the set $[a]$, the ones that are colored by $2$,counted $\binom{m}{h}S_{h,k-r}$ and the ones that are colored by $0,1$ counted $2^{m-h}S_{m-h,r}$.
In the recursion, the process is the same but adding in each step a new element. So $cA_{a-1,b,c}$ is the number of ways you can put a new element colored by $2$ in the $c$ blocks you have, $A_{a-1,b-1,c-1}$ is to create a new block with the new element colored by $2$, $2(b-c)A_{a-1,b,c}$ is to put a new element colored by $0$ or $1$ in the $b-c$ blocks and $2A_{a-1,b-1,c}$ is to create a new class to put a new element colored by $0$ or $1$.
I do not know how to come up with a closed expression but i hope this helps.