# Simple recurrence relation in three dimensions

I have the following recurrence relation:

$$f[i,j,k] = f[i-1,j,k] + f[i,j-1,k] + f[i,j,k-1],\quad \mbox{for } i \geq j+k,$$

starting with $f[0,0,0]=1$, for $i$, $j$, and $k$ non-negative.

Is there any way to find a closed form expression for $f[i,j,k]$?

Note that this basically is a three dimensional version of the Catalan triangle, for which $f[i,j] = f[i-1,j] + f[i,j-1]$, for $i \geq j$, starting with $f[0,0]=1$. For this, a closed form expression is known: $f[i,j] = \frac{(i+j)!(i-j+1)}{j!(i+1)!}$.

-
Is $f[i,j,k]$ defined when $i\lt j+k$? – Will Orrick May 29 '12 at 16:20
I assume $f(i,j,k)=0$ if any of $i,j,k$ are negative, otherwise I don't see how you've defined $f(2,0,1)$ with this recursion – Thomas Andrews May 29 '12 at 16:58
@Will: For consistency with Catalan’s triangle it has to be $0$ when $i<j+k$. – Brian M. Scott May 29 '12 at 23:36
Indeed, I should have specified in the problem statement that $f[i,j,k]=0$ if any of $i,j,k$ are negative, and that $f[i,j,k]=0$ if $i<j+k$. – Wav May 30 '12 at 19:41

With the constraint $i \geq j+k$ I got following formula (inspired by the Fuss-Catalan tetrahedra formula page 10 and with my thanks to Brian M. Scott for pointing out my errancies...) : $$f[i,j,k]=\binom{i+1+j}{j} \binom{i+j+k}{k} \frac{i+1-j-k}{i+1+j}\ \ \text{for}\ i \geq j+k\ \ \text{and}\ \ 0\ \ \text{else}$$

plane $k=0$
$\begin{array} {lllll|lllll} 1\\ 1 & 1\\ 1 & 2 & 2\\ 1 & 3 & 5 & 5\\ 1 & 4 & 9 & 14 & 14\\ \end{array}$

plane $k=1$
$\begin{array} {l} 0\\ 1 \\ 2 & 4\\ 3 & 10 & 15\\ 4 & 18 & 42 & 56\\ 5 & 28 & 84 & 168 & 210\\ \end{array}$

plane $k=2$
$\begin{array} {l} 0\\ 0\\ 2 \\ 5 & 15\\ 9 & 42 & 84\\ 14 & 84 & 252 & 420\\ 20 & 144 & 540 & 1320 & 1980\\ \end{array}$

Without the $i \geq j+k$ constrains we get the simple : $$f[i,j,k]=\frac{(i+j+k)!}{i!j!k!}$$

That is the Trinomial expansion (extension of Pascal triangle in 3D : Pascal tetrahedron).

At least with the rules :

• $f[0,0,0]=1$
• $f[i,j,k]=0$ if $i<0$ or $j<0$ or $k<0$
• $f[i,j,k] = f[i-1,j,k] + f[i,j-1,k] + f[i,j,k-1]$ in the remaining cases
-
It’s not: \begin{align*}f[2,2,0]&=f[1,2,0]+f[2,1,0]\\&=0+f[1,1,0]+f[2,0,0]\\&=f[0,1,0]+f[1‌​,0,0]+f[1,0,0]\\&=0+2f[0,0,0]\\&=2\;.\end{align*} It would probably help to take a look at this. – Brian M. Scott May 29 '12 at 23:33
@Brian: $f[1,1,0]$ should appear 2 times in the second line (+2 contribution) and $f[0,2,0]=1$ is missing (+1). Another +1 is missing for a total of 6. – Raymond Manzoni May 29 '12 at 23:39
I made that mistake originally, too: $f[1,1,0]$ appears only once, because $f[1,2,0]=0$ and doesn’t split. That’s why I wrote the $0$ term explicitly. – Brian M. Scott May 29 '12 at 23:42
@Brian: Sorry but I still don't get it. For me it's $f[0,2,0]=1$ + $f[1,1,0]=2$ (I don't consider the constraint $i\ge j+k$ but I'll admit that it's perhaps the problem here...) – Raymond Manzoni May 29 '12 at 23:48
That’s exactly the problem. The OP wasn’t really clear, but the statement that it’s a $3$-dimensional analogue of Catalan’s triangle strongly implies that $f[i,j,k]=0$ if $i<j+k$. – Brian M. Scott May 29 '12 at 23:55