Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Many years ago, I discovered the remarkable array (apparently originally discovered by Ramanujan)

 1
 1    3
 2   10   15
 6   40  105  105
24  196  700 1260  945

which is defined by $S(i,j) = i\ S(i-1,j) + (i+j)\ S(i-1,j-1)$ and $S(0,1)=1$, and $S(i,j)=0$ if $j<1$ or $j>i+1$. This array has the remarkable property that the sum of the numbers in the $i$'th row is $(i+1)^{i+1}$. This is not easy to prove. There are three approaches I know to proving this

  1. Generating functions.
  2. Counting subclasses of labeled trees.
  3. Generalizing to a 3-dimensional array of numbers. There are recurrences on two sets of parallel planes, which intersect in the rows. One set of parallel planes contains the array above, and the other set contains a recurrence from which one can immediately deduce the row sums. Proving that these two different sets of recurrences give the same array is straightforward (albeit tedious without computer algebra) using induction.

(See SIAM Review, Problems and Solutions column, Vol. 21, pp. 258-260 (1979).)

The third approach is reminiscent of Wilf and Zeilberger's A = B theory of combinatorial identities, except there you have 3-dimensional arrays with recurrences on three sets of parallel planes. Wilf and Zeilberger's theory does not appear to shed any light on this recurrence.

My question is: does anybody know any other 3-dimensional arrays which have recurrences on two sets of parallel planes, but which do not fall under the A = B theory (so you cannot find a recurrence on a third set of parallel planes)? I would especially be interested in recurrences whose coefficients are polynomials in the coordinates $i,j,k$.

For more information about the connection with labeled trees, although this isn't directly connected with my question, see the papers Chen and Guo, Bijections behind the Ramanujan polynomials and Guo and Zeng, A generalization of the Ramanujan polynomials and plane trees, as well as the references in them.

share|improve this question
    
Fascinating! Any hints what $S(i, j)$ is counting? Also, is there some interesting $q$-analogue story? –  Todd Trimble Nov 4 '10 at 16:44
1  
I'm not sure whether anybody has thought about $q$-analogs for this. For what $S(i,j)$ is counting, look at the references for Neal Sloane's sequence A075856 (research.att.com/~njas/sequences/A075856) or this paper of mine (sciencedirect.com/…). –  Peter Shor Nov 4 '10 at 17:17
    
It seems to me, that there is an error in the above definition. I implemented it in Pari/GP and had to correct the $(i+j)$-term to $(i+j+1)$. Pari/GP \\ use "r" and "c" for row- and col-indexes \\ indexes are based on 1, not 0, so I have to add 1: \\ use "r1","c1" for index into matrix S=matid(dim); for(r=1,dim-1, r1=r+1; S[r1,1]=r!; for(c=1,r, c1=1+c; "c1" S[r1,c1] = r*S[r1-1,c1] + (r+c+1)*S[r1-1,c1-1] ) ) print(S) ; –  Gottfried Helms Nov 25 '10 at 4:17
    
upps, that previous comment goes unformatted. I'll convert it into an answer for readability –  Gottfried Helms Nov 25 '10 at 4:18
3  
A different combinatorial interpretation of your sequence $S(i,j)$ seems to be given in this recent MO question: mathoverflow.net/questions/66929/… The connection is that $S(i,j)$ counts the number of weighted trivalent trees with $(i+3)$ extremal vertices and $j$ internal vertices. The recursion can be interpreted as follows: removing the last extremal vertex from such a tree will either produce a new trivalent tree, or one which can be made trivalent by contracting a single internal vertex. –  Dan Petersen Jun 14 '11 at 9:16

1 Answer 1

It seems to me, that there is an error in the above definition. I implemented it in Pari/GP and had to correct the $(i+j)$-term to $(i+j+1)$.

Pari/GP

\\ use "r" and "c" for row- and col-indexes   
\\ indexes are based on 1, not 0, so I have to add 1:     
\\       use "r1","c1" for index into matrix    
S=matid(dim);
for(r=1,dim-1, r1=r+1;   \\ introduce 1-based index into matrix "r1"  
        S[r1,1]=r!;    
        for(c=1,r,  c1=1+c;     \\ introduce 1-based index into matrix "c1"        
              S[r1,c1] = r*S[r1-1,c1] + (r+c+1)*S[r1-1,c1-1]    
           )    
    )   
 print(S) ;
share|improve this answer
    
I think it's a fencepost error. I started my array in (0,1) and I think you started yours in (0,0). –  Peter Shor Nov 26 '10 at 23:44
    
This Mathematica code agrees with Peter's values: > S[i_,j_]:=S[i,j]=Which[j<1||j>i+1,0,i==0&&j==1,1,True,i S[i-1,j]+(i+j)S[i-1,j-1]]; –  Kevin O'Bryant Nov 15 '11 at 17:27

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.