# Generating function for product of binomial coefficients

In general, if $a(n)$ is an integer sequence with generating function $A(t)$ and $b(n)$ is an integer sequence with generating function $B(t)$, it is not easy to find the generating function $C(t)$ for $c(n)=a(n)b(n)$ in terms of $A$ and $B$, i.e., to find the Hadamard product of $A$ and $B$. However, it is not impossible to do so in some special cases.

I am interested in the case where $a(n) = \binom{N}{n}$ and $b(n) = \binom{M}{n}$, i.e., where the sequences are binomial coefficients. In this case $A(t) = (1+t)^N$ and $B(t) = (1+t)^M$. But what is $C$?

• Wolfram|Alpha gives $_2F_1(-M,-N,;1;x)$; I suspect that if there were a way to express that more elementarily W|A would know about it. Sep 29, 2012 at 7:46
• Hmm ... thanks, that does seem like a reasonable conclusion.
– N F
Sep 29, 2012 at 19:47
• If your still interested: I believe I can answer this using section 1.4 of GouldBK.pdf by Sprugnoli. It used to be available freely but now you have to go through researchgate.net/publication/… . Although I think "fair use" means I could send you a copy. OTOH: I can just write out the solution in "Your Answer". The method falls under "Riordan Array transformations" if you want to search. Mar 30, 2019 at 18:47
• @rrogers I am extremely interested. These polynomials have just come up in my research on random string comparison in a big and surprising way. Would you be able to share Sprugnoli's paper and any insights of yours? I would be happy to tell you more and to acknowledge your help. Mar 20, 2021 at 6:25
• Here is a temporary copy (and email), please download soon. I will take it down shortly:dropbox.com/sh/p0kl17awlxx15on/AAB-Gsw-prWZO87Ey8EfgQ-ka?dl=0 Let me know when you copy; through here. Hopefully before the Hall monitors descend. Mar 20, 2021 at 15:06

Here is a "solution" that might be useful; but it is not wholly satisfactory.
(as usual read carefully before using (sigh!))
We use the “Snake Oil Method” from Wilf's book “generatingfunctionology” (second edition) Amazon
or free: Free version
A good book in either form. Chapter 4, page 125 and following the example on 126. We get:
$$\left(\begin{array}{c} N\\ n \end{array}\right)\left(\begin{array}{c} M\\ n \end{array}\right)= \left[t^{n}\right]\left[s^{N}\right]\frac{1}{1-s}\cdot\left(1+\frac{\left(t\cdot s\right)}{\left(1-s\right)}\right)^{M}$$
Let
$$F(N,M,n;t)=\displaystyle \sum_{n=0}\left(\begin{array}{c} N\\ n \end{array}\right)\left(\begin{array}{c} M\\ n \end{array}\right)t^{n}$$
We “dodge the bullet” and sum on an independent parameter N and variable s. In this case it's easy to undo afterwards.
$$f(M,N;s,t)=\sum_{n=0}\left(\begin{array}{c} i\\ n \end{array}\right)\left(\begin{array}{c} M\\ n \end{array}\right)t^{n}s^{i}=\sum_{n=0}}}}\left(\begin{array}{c} M\\ n \end{array}\right)t^{n}\cdot\sum_{i=0}}\left(\begin{array}{c} i\\ n \end{array}\right)s^{i}$$
$$=\sum_{n=0}}}\left(\begin{array}{c} M\\ n \end{array}\right)\cdot t^{n}\cdot\frac{s^{n}}{\left(1-s\right)^{n+1}}=\frac{1}{1-s}\cdot\sum_{n=0}}}\left(\begin{array}{c} M\\ n \end{array}\right)\cdot\frac{\left(t\cdot s\right)^{n}}{\left(1-s\right)^{n}}=\frac{1}{1-s}\cdot\left(1+\frac{\left(t\cdot s\right)}{\left(1-s\right)}\right)^{M}$$
Now it's obvious how to pick out $$t^{n}$$
$$\left[t^{n}\right]\frac{1}{1-s}\cdot\left(1+\frac{\left(t\cdot s\right)}{\left(1-s\right)}\right)^{M}=\frac{1}{1-s}\cdot\left(\begin{array}{c} M\\ n \end{array}\right)\cdot\left(\frac{\left(s\right)}{\left(1-s\right)}\right)^{n}$$
And $$s^{N}$$
$$\left[s^{N}\right]\frac{1}{1-s}\left(\frac{\left(s\right)}{\left(1-s\right)}\right)^{n}=\left[s^{N-n}\right]\frac{1}{\left(1-s\right)^{n+1}}=\left(\begin{array}{c} n+\left(N-n\right)\\ N-n \end{array}\right)=\left(\begin{array}{c} N\\ N-n \end{array}\right)=\left(\begin{array}{c} N\\ n \end{array}\right)$$
But not what we would prefer.
$$\left[s^{N}\right]\frac{1}{1-s}\cdot\left(1+\frac{\left(t\cdot s\right)}{\left(1-s\right)}\right)^{M}$$ to leave $$\left[t^{n}\right]$$

Which I can't see how to do.