Blogrolling On II

Recall that binary trees satisfied the Catalan relation $T = 1 + T^{2}$, whereas Schroeder numbers, or Motzkin numbers, satisfy the substitution rule $X = 1 + X + X^{2}$. In this paper, Cossali studies a generalisation of the generating function for the Catalan numbers $C_{n}$. Let

$L(x,z) = \sum_n \sum_m C_{m} B(2m + n, n) x^m z^n = J(x, z/x)$

where $B(i,j)$ is the binomial coefficient. The substitution rules above are all united by the function $J(x,y)$ which satisfies the rule

$xJ^{2} + xy J + 1 = J$

When $x = 1$ and $y = 0$ this reduces to $J = 1 + J^{2}$, the rule for counting the number of vertices on an associahedron, but when $x = y = 1$ it reduces to the rule $J^{2} + J + 1 = J$. In general, the generating function takes the form

$J(x,y) = \frac{1}{2x} [(1 – yx) \pm \sqrt{(1 – yx)^{2} – 4x}]$

Note that the coefficients $g(m,n) = C_{m} B(2m + n, n)$ of the double series $L(x,z)$ could only give the Schroeder numbers when $x = z$, so by summing the diagonals of the table on page 4 (that is, summing the $g(m,n)$ of weight $i$, starting with $g(0,0) = 1$ for $i = 0$) the Schroeder numbers are obtained. This proves that the Schroeder numbers $S_{i}$ are given by

$S_{i} = \sum_{m + n = i} C_m B(2m + n, n)$

which is a little nicer than the hypergeometric expression $2F1 (1 – i, 2 + i ; 2;-1)$. By setting $y = -1$ the coefficients are alternating sums of the $g(m,n)$ and this leads to the sequence $1,0,0,0,0,0,…$ The Motzkin rule follows from setting $y = \sqrt{x}^{-1}$ and then working with $z = \sqrt{x}$, which one may verify by looking at the generating function. Can we generate more cute Abel sums using $J(x,y)$?


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: