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
    Is $f[i,j,k]$ defined when $i\lt j+k$?2012-05-29
  • 0
    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 recursion2012-05-29
  • 0
    @Will: For consistency with [Catalan’s triangle](http://mathworld.wolfram.com/CatalansTriangle.html) it has to be $0$ when $i.2012-05-29
  • 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
    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](http://mathworld.wolfram.com/CatalansTriangle.html).2012-05-29
  • 0
    @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.2012-05-29
  • 0
    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.2012-05-29
  • 0
    @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...)2012-05-29
  • 1
    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](http://mathworld.wolfram.com/CatalansTriangle.html) strongly implies that $f[i,j,k]=0$ if $i.2012-05-29
  • 0
    Thanks a lot for the formula and the reference to the Fuss-Catalan tetrahedra. However, I expect the plane $k=1$ to become $$ \begin{array}{cccc} 0 \\ 1 \\ 2 & 4 \\ 3 & 10 & 15 &\\ 4 & 18 & 42 & 56 \end{array} $$ as, e.g., $$ f[2,1,1] = f[1,1,1] + f[2,0,1] + f[2,1,0] = 0 + 2 + 2 = 4 $$ instead of 3. The Fuss-Catalan tetrahedra has a slightly different recursion, with one extra term subtracted: $$f[i,j,k] = f[i-1,j,k]+f[i,j-1,k]+f[i,j,k-1] - f[i,j-1,k-1]$$ (see formula 2.1). Maybe the proposed closed-form expression can be adapted for that, but I do not see how that could be done.2012-05-30
  • 0
    @Wav: you are right and I gave it another try (I merely added a $j$ in the second binomial). Please verify my third release!2012-05-30
  • 0
    Great, exactly the solution to the recursion I was looking for. Thanks!2012-06-04
  • 0
    @Wav: you are welcome!2012-06-04