5
$\begingroup$

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
$\endgroup$
5
$\begingroup$

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.

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

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].$$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Why is $a_n=$OEIS A258109? $\endgroup$ – Liviu Nicolaescu Dec 12 '18 at 13:34
  • $\begingroup$ Is it possible to prove result? $\endgroup$ – 1Spectre1 Dec 12 '18 at 13:48
  • 2
    $\begingroup$ 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. $\endgroup$ – EFinat-S Dec 12 '18 at 14:49

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.