# generating function of multinomial coefficient

How to express this series in closed form? $$\sum_{i=1}^{\infty}\frac{(3i)!}{(i!)^3}x^{i}$$

Motive of the generating function is to evaluate the number of the paths from the $(0,0,0)$ to $(n,n,n)$ not passing through $(i,i,i)$ ($1\leq i\leq n-1)$. The answer is coefficient of $x^n$ in $$\sum_{k=1}^{n}(-1)^{k-1}\left(\sum_{i=1}^{n}\frac{(3i)!}{(i!)^3}x^{i}\right)^{k}.$$

-
Not really an answer but Mathematica yields: $$-1+\,_{2}F_{1}\left(\left.{\frac{1}{3},\frac{2}{3}\atop 1}\right|27x\right)$$ Are you sure there's a closed form? – Shaktal Aug 28 '12 at 13:31
see De Bruijn's S(3,n) at OEIS. You should find Shaktal's answer for example ! – Raymond Manzoni Aug 28 '12 at 13:31

The summand $c_n = x^n (3n)!/(n!)^3$ is a hypergeometric term, meaning that $c_{n+1}/c_n$ is a rational function of $n$. Indeed: $$\frac{c_{n+1}}{c_n} = \frac{x^{n+1}}{x_n} \frac{(3n+3)!}{(3n)!} \left(\frac{n!}{(n+1)!}\right)^3 = x \frac{(3n+3)(3n+2)(3n+1)}{(n+1)^3} = 27 x \frac{\left(n+\frac{1}{3}\right)}{(n+1)} \frac{\left(n+\frac{2}{3}\right)}{(n+1)}$$ Such a recurrence equation implies that $$c_n = c_0 \prod_{k=0}^{n-1} 27 x \frac{\left(k+\frac{1}{3}\right)}{(k+1)} \frac{\left(k+\frac{2}{3}\right)}{(k+1)} = c_0 \frac{(27 x)^n}{n!} \frac{\left(\frac{1}{3}\right)_n \left(\frac{2}{3}\right)_n}{(1)_n}$$ Now the sum in question get's written as a defining series of the Gauss hypergeometric function: $$\sum_{i=0}^\infty \binom{3i}{i,i,i} x^i = \sum_{n=0}^\infty \frac{(27 x)^n}{n!} \frac{\left(\frac{1}{3}\right)_n \left(\frac{2}{3}\right)_n}{(1)_n} = {}_2F_1\left(\frac{1}{3}, \frac{2}{3}; 1; 27 x\right)$$ The result for summation from $i=1$ is obtained by subtracting the first term.
$$6 \,x \,{ _3F_{2}\left(1,\frac{4}{3},\frac{5}{3};\,2,2;\,27\,x\right)}\,.$$