A certain sum of multinomial coefficients

Question

I would like to know if there is a nice expression for the sum $$ S(n)=\sum_{i+j=n}\binom{3i}{i,i,i}\binom{3j}{j,j,j} $$ where $n$ is a non-negative integer. I have entered in the first few values of $S(n)$ to OEIS and gotten no results.

A similar looking sum which does have a nice expression is $$ T(n)=\sum_{i+j=n}\binom{2i}{i}\binom{2j}{j}=4^n $$ A reference for this is "New developments of an old identity"-Rui Duarte and Antonio Guedes de Oliveira (https://arxiv.org/abs/1203.5424)

Answer 1

I suspect there is no closed form. Using Zeilberger's algorithm, you can show that the minimal recurrence relation with polynomial coefficients satisfied by $S(n)$ is $$ 27(3n+2)(3n+3)(3n+4)S(n)-3(2n+3)(9n^2+27n+22)S(n+1)+(n+2)^3S(n+2)=0 $$ Then, using Petkovšek's algorithm, you can show that this recurrence has no hypergeometric solutions. This means that $S(n)$ has no closed form involving only addition, multiplication, exponentiation with constant base, and the gamma function. I cannot rule out the possibility of a closed form involving expressions like $n^n$, but I have never seen something like that happen before with a summation of products of binomial coefficients.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{{\displaystyle #1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\on}[1]{\operatorname{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\sr}[2]{\,\,\,\stackrel{{#1}}{{#2}}\,\,\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \color{#44f}{\on{S}}\pars{n} & \equiv \color{#44f}{\sum_{i\ +\ j\ =\ n} {3i \choose i\ i\ i}{3j \choose j\ j\ j}} = \sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty} {3i \choose i\ i\ i}{3j \choose j\ j\ j}\bracks{z^{n}}z^{i + j} \\[5mm] & = \bracks{z^{n}}\bracks{\sum_{i = 0}^{\infty}{3i \choose i\ i\ i}z^{i}}^{2} = \bracks{z^{n}}\bracks{\sum_{i = 0}^{\infty}{\pars{3i}! \over i!^{3}}z^{i}}^{2} \\[5mm] & = \bracks{z^{n}}\bracks{\mbox{}_{2}\!\on{F}_{1}\pars{\left.\begin{array}{c} \ds{1/3\quad 2/3} \\ 1 \end{array}\right\vert 27z}}^{2} \\[5mm] & \underline{\ds{It\ doesn't\ seem\ very\ use\!ful\,!!!.}} \end{align}