45

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 Peter Shor, Otto G. Ruehr, 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.

darij grinberg
  • 33,095
Peter Shor
  • 6,272
  • Fascinating! Any hints what $S(i, j)$ is counting? Also, is there some interesting $q$-analogue story? – Todd Trimble Nov 04 '10 at 16:44
  • 2
    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 (http://www.research.att.com/~njas/sequences/A075856) or this paper of mine (http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHS-4D0YBBG-26&_user=501045&_coverDate=07%2F31%2F1995&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_acct=C000022659&_version=1&_urlVersion=0&_userid=501045&md5=1a2978f3fa0cbe42f4d383e5529d6171&searchtype=a). – Peter Shor Nov 04 '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] = rS[r1-1,c1] + (r+c+1)S[r1-1,c1-1]
    )
    )
    print(S) ;

     – Gottfried Helms Nov 25 '10 at 04:17
  • upps, that previous comment goes unformatted. I'll convert it into an answer for readability – Gottfried Helms Nov 25 '10 at 04:18
  • 3
    A different combinatorial interpretation of your sequence $S(i,j)$ seems to be given in this recent MO question: http://mathoverflow.net/questions/66929/number-of-weighted-trivalent-trees

    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 09:16
  • 3
    For the sake of future readers, let me quote a remark from the SIAM review solution: "By essentially the same inductive argument one can show that the more general recursion relation $S\left(m+1,n\right) = \left(m+z\right) S\left(m,n\right) + \left(m+n\right) S\left(m,n-1\right)$ has a solution satisfying $\sum\limits_{n=1}^m S\left(m,n\right) = \left(m+z\right)^m$". – darij grinberg Jul 09 '21 at 21:47
  • 1
    It is also worth noting that this general recursion relation is a particular case of the Graham--Knuth--Patashnik recurrence for $\alpha = 1$, $\beta = 0$, $\gamma = z+1$, $\alpha' = 1$, $\beta' = 1$ and $\gamma' = 1$, although the initial condition is off by a $1$ on the second argument. I don't know if the Salas--Sokal paper says anything interesting about this case, though. – darij grinberg Jul 09 '21 at 21:51
  • 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] = rS[r1-1,c1] + (r+c+1)S[r1-1,c1-1] ) ) print(S) ; – Gottfried Helms Nov 25 '10 at 04:20

0 Answers0