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



Formula for a sum of product of binomials
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](https://oeis.org/A258109) as length $2(n-1)$ depth $k$ nested balanced parantheses expressions / plane trees / Dyck paths, which will thus be related to a column of[OEIS A080936](https://oeis.org/A080936).


