# Formula for a sum of product of binomials

We know that equation $$s_1+s_2+s_3=n-1 \quad \mbox{s_1,s_2,s_3}\geq 1$$ has $$\binom{n-2}{2}$$ solution. I want to find any good formulae for the following form :

$$\sum_{(s_1,s_2,s_3)}\prod_{i=1}^3\binom{s_i+s_{i-1}-1}{s_i}=?$$ where, $$s_0=1$$ and each $$(s_1,s_2,s_3)$$ is the solution of above equation.

I find that following: $$n=4\Longrightarrow 1$$ $$n=5\Longrightarrow 5$$ $$n=6\Longrightarrow 18$$ $$n=7\Longrightarrow 57$$ $$n=8\Longrightarrow 169$$ $$n=9\Longrightarrow 502$$

• My all attempts have failed

The generating function is $$\sum_{s_1,s_2, s_3} {s_1 + s_2-1 \choose s_2} {s_2+ s_3-1 \choose s_3} x^{s_1+s_2+s_3}.$$

$$\sum_{s_3} {s_2+ s_3-1 \choose s_3} x^{s_3} = \left( \frac{1}{1-x}\right)^{s_2}$$.

Then the sum over the $$s_2$$ variable is

$$\sum_{s_2} {s_1 + s_2-1 \choose s_2}\left( \frac{x}{1-x}\right)^{s_2} = \left( \frac{1}{1- \frac{x}{1-x}} \right)^{s_1} = \left( \frac{1-x}{1-2x} \right)^{s_1}$$

and the sum over just the $$s_1$$ variable is

$$\sum_{s_1} \left( \frac{x-x^2}{1-2x}\right)^{s_1} = \frac{1}{1- \frac{x-x^2}{1-2x}}=\frac{1-2x}{1-3x+x^2}.$$

However, we need to remove the terms when $$s_1,s_2$$ or $$s_3$$ is zero. Because of the binomial coefficients, if $$s_1$$ vanishes then $$s_2$$ vanishes and if $$s_2$$ vanishes then $$s_3$$ vanishes, so it suffices to remove the terms with $$s_3=0$$, which are

$$\sum_{s_1,s_2} {s_1 + s_2-1 \choose s_2} x^{s_1+s_2}= \frac{1-x}{1-2x}$$ by the same logic.

So the full generating function is $$\frac{1-2x}{1-3x+x^2} - \frac{1-x}{1-2x}.$$

Your sum is then the coefficient of $$x^{n-1}$$ in this series. To get this, as EFinat-S suggests we may use partial fractions.

$$\frac{1-2x}{1-3x+x^2} - \frac{1-x}{1-2x} = \frac{- 2 + \sqrt{5} }{1- \frac{3 + \sqrt{5}}{2} x} + \frac{-2-\sqrt{5} }{1- \frac{3 - \sqrt{5}}{2} x} - \frac{1/2}{1-2x} - \frac{1}{2}$$

which will match the expression Carlo Beenaker gave.

Moreover, this will generalize to the analogue with $$s_1,\dots,s_k$$, giving a rational generating function. There is a straightforward enumerative interpretation, along the lines of the OEIS reference Carlo found as length $$2(n-1)$$ depth $$k$$ nested balanced parantheses expressions / plane trees / Dyck paths, which will thus be related to a column ofOEIS A080936.

• Can we obtain formulae for $s_1+s_2+s_3+s_4=n-1$ ? – 1ENİGMA1 Dec 12 '18 at 16:48
• @1ENİGMA1 Yes, the same method works. – Will Sawin Dec 12 '18 at 19:18
• @WillSawin In OEIS A080936, I couldn't see how to compute this: $T(n, k) = A080934(n, k) - A080934(n, k-1).$ – 1Spectre1 Dec 13 '18 at 13:17
• @1Spectre1 It's obvious. One counts paths of height $\leq k$, the other of height $=k$, so subtracting cancels the lower-height paths. – Will Sawin Dec 13 '18 at 14:07

Inspection of the Mathematica output

In: Table[Sum[Binomial[s2 + s1 - 1, s2]* Binomial[n - s1 - 2, n - 1 - s1 - s2], {s2, 1, n - 3}, {s1, 1,  n - 2 - s2}], {n, 4, 20}]
Out: {1, 5, 18, 57, 169, 482, 1341, 3669, 9922, 26609, 70929, 188226, 497845, 1313501, 3459042, 9096393, 23895673}


indicates it's the series OEIS A258109 $$a_n=\frac{1}{5} 2^{-n-1} \left[\left(\sqrt{5}+5\right) \left(3-\sqrt{5}\right)^n-5\ 4^n-\left(\sqrt{5}-5\right) \left(\sqrt{5}+3\right)^n\right].$$

• Why is $a_n=$OEIS A258109? – Liviu Nicolaescu Dec 12 '18 at 13:34
• Is it possible to prove result? – 1Spectre1 Dec 12 '18 at 13:48
• A "not very nice" idea is that your formula should satisfy a recurrence relation. Encode it in a power series, use decomposition into partial fractions and obtain another power series such that its coefficients are the $a_n$; just like for the explicit formula for Fibonacci numbers. – EFinat-S Dec 12 '18 at 14:49