45
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ Fascinating! Any hints what $S(i, j)$ is counting? Also, is there some interesting $q$-analogue story? $\endgroup$
    – Todd Trimble ♦
    Nov 4, 2010 at 16:44
  • 2
    $\begingroup$ 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/…). $\endgroup$
    – Peter Shor
    Nov 4, 2010 at 17:17
  • $\begingroup$ 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) ; $\endgroup$
    – Gottfried Helms
    Nov 25, 2010 at 4:17
  • 3
    $\begingroup$ 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. $\endgroup$
    – Dan Petersen
    Jun 14, 2011 at 9:16
  • 2
    $\begingroup$ 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$". $\endgroup$
    – darij grinberg
    Jul 9, 2021 at 21:47

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.