46
$\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
    Commented 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
    Commented Nov 4, 2010 at 17: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
    Commented Jun 14, 2011 at 9:16
  • 3
    $\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
    Commented Jul 9, 2021 at 21:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – darij grinberg
    Commented Jul 9, 2021 at 21:51

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .