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$?

Thanks in advance for any advice or references!

  • 2
    $\begingroup$ 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. $\endgroup$
    – joriki
    Sep 29, 2012 at 7:46
  • $\begingroup$ Hmm ... thanks, that does seem like a reasonable conclusion. $\endgroup$
    – N F
    Sep 29, 2012 at 19:47
  • $\begingroup$ 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. $\endgroup$
    – rrogers
    Mar 30, 2019 at 18:47
  • $\begingroup$ @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. $\endgroup$ Mar 20, 2021 at 6:25
  • $\begingroup$ 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. $\endgroup$
    – rrogers
    Mar 20, 2021 at 15:06

1 Answer 1


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}$
$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)={\displaystyle \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}={\displaystyle {\displaystyle \sum_{n=0}}}}\left(\begin{array}{c} M\\ n \end{array}\right)t^{n}\cdot{\displaystyle \sum_{i=0}}\left(\begin{array}{c} i\\ n \end{array}\right)s^{i}$
$={\displaystyle {\displaystyle \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{\displaystyle {\displaystyle \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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.