1
$\begingroup$

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)!}$.

Appreciate your help!

  • 0
    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.2012-05-30

1 Answers 1

2

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
  • 0
    @Wav: you are welcome!2012-06-04