Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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
share|improve this answer
    
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
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 strongly implies that $f[i,j,k]=0$ if $i<j+k$. –  Brian M. Scott May 29 '12 at 23:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.