# A Vandermonde Identity for Stirling Numbers?

I'm facing the problem of trying to express a quantity in the simplest possible way (it is, using the least possible number of sum symbols).

$$\sum_{j=0}^{n} \sum_{\ell=0}^m \frac{1}{j!}\binom{b+j}{j} {j+1 \brack {\ell+1}} {b+2 \brack {m-\ell+1}}$$

Of course, this can be easily written as a convolution between two polynomials (which happen to be more or less simple). I'm pretty sure that approach will not work (at most, one can write the above expression as "the coefficient of $$x^m$$ in this product [...]", but that is not useful to my purpose).

However, if one explores this sum a little bit, it pretty soon come up the fact that it could be truly useful to, for example, be able to compute this: $$\sum_{\ell=0}^m {j+1\brack{\ell+1}}{b+2 \brack {m-\ell+1}}$$ (which resembles a lot Vandermonde's Identity, but with Stirling numbers instead of binomial coefficients).

I looked up on a couple of books (Concrete Mathematics of Graham-Knuth-Patashnik, and others), and I couldn't find any references pointing to such an identity. Does anybody know something like that? (Perhaps involving other weird numbers as Eulerian or double Eulerian or that kind of stuff?)

Nevertheless, any kind of help simplifying the first double sum would be really appreciated.

• The case $j=b=m$ yields OEIS A187235. Feb 16, 2020 at 13:46
• Do you want a simple or elementary answer? And a simple or elementary derivation? I think I can see a way forward but it involves several (elementary!) expansions and detours through calculus. Basically generate the generating function around the parameters b,m,n. Which will (?) generate first-order differential equations; that have to be reinserted in the first equation. I would guess that the answer would be some form of Generalized Hypergeometric Functions. Of course, I could be off-base :) Feb 19, 2020 at 17:54
• I don't mind if the derivation is hard (any kind of machinery is allowed). However, if the obtained formula ends up being a lot harder to compute than the original one, probably it wouldn't be so meaningful. Nevertheless, it may be the case that what you have is possibly useful, so please share it :) Feb 19, 2020 at 19:50
• Making progress; are you sure that "m" isn't constrained? Letting it get very large produce's large terms even for low "j". And your Stirling symbol means "unsigned Stirling", right? Is there any constraint on "B"? The binomial form can be thrown via the Riordan transform. With suitable constraints, a neat result can be fabricated, maybe. Feb 20, 2020 at 17:04
• I can post the primary tools I am using if you want. There are more than is convenient in comments. Feb 20, 2020 at 17:06

We show the following identity is valid for non-negative integers $$a,b,M$$: \begin{align*} \sum_{k=0}^M {a\brack k}{b\brack M-k}=\sum_{n=0}^{\min{\{a,b\}}}{a+b-n\brack M}\frac{(-1)^na!b!}{n!(a-n)!(b-n)!}\tag{1} \end{align*}

The right-hand sum is regrettably not a simplification. But we have at least one factor as Stirling number of the first kind instead of two (at the cost of some other factors) and we have an upper index containing $$a+b$$ which comes somewhat close to Vandermonde's identity \begin{align*} \sum_{k=0}^m\binom{a}{k}\binom{b}{M-k}=\binom{a+b}{M} \end{align*}

We show (1) by recalling the generating function: \begin{align*} (1-z)^{-u}=\sum_{n=0}^\infty\sum_{k=0}^n{n\brack k}u^k\frac{z^n}{n!}\tag{2} \end{align*}

At first we derive the left-hand side of (1). We use the coefficient of operator $$[z^n]$$ to denote the coefficient of $$z^n$$ and obtain from (2) \begin{align*} \color{blue}{a!b!}&\color{blue}{[u^Mz^at^b](1-z)^{-u}(1-t)^{-u}}\tag{3}\\ &=a!b![u^M]\left([z^a]\sum_{n=0}^\infty\sum_{k=0}^n{n\brack k}u^k\frac{z^n}{n!}\right)\left([t^b]\sum_{n=0}^\infty\sum_{k=0}^n{n\brack k}u^k\frac{t^n}{n!}\right)\\ &=a!b![u^M]\left(\sum_{k=0}^a{a\brack k}u^k\frac{1}{a!}\right)\left(\sum_{l=0}^b{b\brack l}u^l\frac{1}{b!}\right)\\ &=[u^M]\sum_{q=0}^{a+b}\sum_{{k+l=q}\atop{k,l\geq 0}}{a\brack k}{b\brack l}u^q\\ &=[u^M]\sum_{q=0}^{a+b}\sum_{k=0}^q{a\brack k}{b\brack q-k}u^q\\ &\,\,\color{blue}{=\sum_{k=0}^M{a\brack k}{b\brack M-k}}\tag{4} \end{align*}

We take (3) and calculate the coefficient in a somewhat different way.

We obtain \begin{align*} \color{blue}{a!b!}&\color{blue}{[u^Mz^at^b]((1-z)(1-t))^{-u}}\\ &=a!b![u^Mz^at^b](1-(z(1-t)+t))^{-u}\\ &=a!b![u^Mz^at^b]\left(\sum_{n=0}^\infty\sum_{k=0}^n{n\brack k}u^k\frac{(z(1-t)+t)^n}{n!}\right)\tag{5}\\ &=a!b![z^at^b]\sum_{n=0}^\infty{n\brack M}\frac{(z(1-t)+t)^n}{n!}\tag{6}\\ &=a!b![z^at^b]\sum_{n=0}^\infty{n\brack M}\frac{1}{n!}\sum_{j=0}^n\binom{n}{j}z^j(1-t)^jt^{n-j}\tag{7}\\ &=a!b![t^b]\sum_{n=0}^\infty{n\brack M}\frac{1}{n!}\binom{n}{a}(1-t)^at^{n-a}\tag{8}\\ &=a!b!\sum_{n=0}^{\min\{a,b\}}{n\brack M}\frac{1}{n!}\binom{n}{a}\binom{a}{a+b-n}(-1)^{a+b-n}\tag{9}\\ &=a!b!\sum_{n=0}^{\min\{a,b\}}{n\brack M}\frac{(-1)^{a+b-n}}{(n-a)!(n-b)!(a+b-n)!}\tag{10}\\ &\,\,\color{blue}{=a!b!\sum_{n=0}^{\min{\{a,b\}}}{a+b-n\brack M}\frac{(-1)^n}{n!(a-n)!(b-n)!}}\tag{11} \end{align*} and the claim (1) follows.

Comment:

• In (5) we expand the series according to (2).

• In (6) we select the coefficient of $$u^M$$.

• In (7) we expand the binomial.

• In (8) we select the coefficient of $$z^a$$.

• In (9) we select the coefficient of $$t^b$$.

• In (10) we do some cancellations.

• In (11) we change the order of summation $$n\to a+b-n$$.

• @LuisFerroni: Many thanks for granting the bounty. Feb 23, 2020 at 6:18
• 1) Nice proof, much better than my futile attempts. 2) I was applying Zeilberg's algorithm (via Reduce) to apply binomial(b+a,b) to (9) (for a warmup to (b-3+a,b-2) ) and noticed that your transition (9) to (10) doesn't work. Consider n<a (i.e. n=1,a=10 or b=2) then the factorial interpretation of the binomial() blows up in (10). I think you have to go to the Gamma interpretation of the binomial when going from (9) to (10); to get zeros in the right place. Feb 27, 2020 at 13:43
• @rrogers: Thanks for your nice comment. Here I consider formal power series. So, a switch to Gamma function is for this kind of derivation not necessary. Feb 27, 2020 at 14:30
• Okay, would you be upset if I posted the application of the binomial(b+a, a) to eliminate the "a"? Your development was really nice, in that exposed it. I have yet to be able to phrase the Stirling term but there is one clue. Feb 27, 2020 at 15:21
• @rrogers: This is fine for me. The more useful ideas are contributed, the better for the community. Feb 27, 2020 at 15:53

As usual check carefully (although there is a code snippet to illustrate).
I seem to have a form of mathematical dyslexia.
Answer: $$\left[x^{M}\right]\frac{\Gamma\left(x+a\right)\Gamma\left(x+b\right)}{\Gamma\left(x\right)\Gamma\left(x+a+b\right)}\left(x\right)_{\left(a+b\right)}$$
Actually the expression gives the answer for all $$M$$. Some code is included for that. I can expand it to include M and the binomial summation on a if needed. The process can probably be specialized to just compute one answer for a particular $$M$$. Let me know if you need it.

First some standard facts:
Definition 1. The Pochhammer symbol.

\begin{align*}\left(x\right)_{n}=x\cdot\left(x+1\right)\ldots\left(x+n-1\right) \end{align*}

Definition 2. Unsigned Stirling Number
$$\left[\begin{array}{c} n\\ l \end{array}\right]\equiv\left[x^{l}\right]{\displaystyle \prod_{k=0}^{n-1}\left(x+k\right)=\left[x^{l}\right]x\cdot\left(x+1\right)\ldots\left(x+n-1\right)}=\left[x^{l}\right]\left(x\right)_{n}$$
$$=\left[x^{l}\right]{\displaystyle \sum_{j=0}^{n}}\left[\begin{array}{c} n\\ j \end{array}\right]x^{j}$$

We can partition

$$\left(x\right)_{\left(a+b\right)}\rightarrow\left(x\right)_{a}\cdot\left(x+a\right)_{b} \tag{1}\label{1}$$

The formula for all convolutions:

$$(x)_{a}\cdot\left(x\right)_{b} \tag{2}\label{2}$$
The problem can be phrased as the convolution : $${\displaystyle {\displaystyle \sum_{j=0}^{min\left(a,b,M\right)}}\,\left[\begin{array}{c} a\\ j \end{array}\right]\left[\begin{array}{c} b\\ M-j \end{array}\right]}={\displaystyle \sum_{j=0}^{min\left(a,b\right)}}\left(\left[x^{j}\right]\left(x\right)_{a}\right)\cdot\left(\left[x^{M-j}\right]\left(x\right)_{b}\right)$$
$$=\left[x^{M}\right]\left(\left(x\right)_{a}\cdot\left(x\right)_{b}\right) \tag{2}\label{3}$$
Remark. The upper limit can be extended but additional terms would be zero.
The intent is to convert (1) to (2). Which can be done using:
http://functions.wolfram.com/06.10.17.0004.02
Substituting our symbols.
$$\left(x\right)_{b}=\frac{\Gamma\left(x+a\right)\Gamma\left(x+b\right)}{\Gamma\left(x\right)\Gamma\left(x+a+b\right)}\left(x+a\right)_{b}$$
Which is so obvious it's laughable.
$$\left[x^{M}\right]\frac{\Gamma\left(x+a\right)\Gamma\left(x+b\right)}{\Gamma\left(x\right)\Gamma\left(x+a+b\right)}\left(x\right)_{\left(a+b\right)}=\left[x^{M}\right]\left(x\right)_{a}\cdot\left(x\right)_{b}$$
load ("stirling")$$gamma_expand: true$$