TAOCP 7.2.1.6 Exercise 47

Exercise 47. [M27] Continuing the previous exercise, generalize the identity (27).

Verified: no
Solve time: 25m34s

Setup

We work with the polynomials (C_{pq}(x)) defined in Exercise 46: [ C_{pq}(x) = x^{p-q-1}C_{p-1,q}(x) + x^{q}C_{p-1,q-1}(x) \qquad (0\le p\le q,; q\ne 0), ] with (C_{00}(x)=1) and (C_{pq}(x)=0) for (p<0) or (p>q).
The diagonal polynomials are (C_n(x)=C_{nn}(x)); their generating function is [ C(x,z) = \sum_{n=0}^\infty C_n(x),z^n. ] Equation (27) of the text is the generating function for the ordinary Catalan numbers [ C(z) = 1 + z,C(z)^2, ] and Exercise 46(c) shows its generalization to the Narayana polynomials: [ C(x,z) = 1 + z,C(x,z),C(x,xz). \tag{27} ]

We are asked to continue the generalization to the full bivariate family (C_{pq}(x)).
Define the bivariate generating function [ F(u,v) = \sum_{p=0}^\infty\sum_{q=p}^\infty C_{pq}(x),u^p v^q. ]

Solution

Multiply the recurrence for (C_{pq}(x)) by (u^p v^q) and sum over (p\ge 1), (q\ge p) (the case (p=0) gives (C_{0q}=0) for (q>0) and is already accounted for by the constant term (C_{00}=1)):

[ \sum_{p\ge 1,,q\ge p} C_{pq},u^p v^q = \sum_{p\ge 1,,q\ge p} x^{p-q-1}C_{p-1,q},u^p v^q

\sum_{p\ge 1,,q\ge p} x^{q}C_{p-1,q-1},u^p v^q. ]

The left‑hand side is (F(u,v)-1). For the first sum set (i=p-1), (j=q); then (p=i+1), (q=j) with (i\ge 0), (j\ge i+1): [ \begin{aligned} \sum_{i\ge 0,,j\ge i+1} x^{i-j}C_{i,j},u^{i+1}v^j &= u\sum_{i\ge 0,,j\ge i} x^{i-j}C_{i,j}u^i v^j

u\sum_{i\ge 0} C_{i,i},u^i v^i \ &= u,F(ux,,vx^{-1}) - u,C(x,uv). \end{aligned} ]

For the second sum set (i=p-1), (j=q-1); then (p=i+1), (q=j+1) with (i\ge 0), (j\ge i): [ \sum_{i\ge 0,,j\ge i} x^{j+1}C_{i,j},u^{i+1}v^{j+1} = uvx\sum_{i\ge 0,,j\ge i} C_{i,j},u^i (vx)^j = uvx,F(u,,vx). ]

Assembling the pieces gives the functional equation [ F(u,v) = 1 + u,F(ux,,vx^{-1}) - u,C(x,uv) + uvx,F(u,,vx). \tag{★} ]

This is the desired generalization of identity (27) to the full bivariate generating function of the polynomials (C_{pq}(x)). It reduces to the diagonal equation (C(x,z)=1+zC(x,z)C(x,xz)) when we set (v=ux) and use the relation (F(u,ux)=C(x,u^2)) (which follows from the definition of (F) and the fact that (C_{pq}=0) for (p>q)).

Verification

We check the first few terms directly from the recurrence: [ \begin{aligned} C_{00}&=1,\ C_{11}&=x^{1-1-1}C_{01}+x^1C_{00}=0+x=x,\ C_{12}&=x^{1-2-1}C_{02}+x^2C_{01}=0,\ C_{22}&=x^{2-2-1}C_{12}+x^2C_{11}=0+x^3=x^3,\ C_{33}&=x^{3-3-1}C_{23}+x^3C_{22}=0+x^6=x^6. \end{aligned} ] Thus [ F(u,v)=1+x,uv + x^3 u^2v^2 + x^6 u^3v^3 + \cdots,\qquad C(x,z)=1+xz + x^3z^2 + x^6z^3 + \cdots. ]

Compute the right‑hand side of (★): [ \begin{aligned} uF(ux,vx^{-1}) &= u\bigl(1 + x(ux)(vx^{-1}) + x^3(ux)^2(vx^{-1})^2 + \cdots\bigr) = u + x u^2v + x^3 u^3v^2 + \cdots,\ uC(x,uv) &= u\bigl(1 + x(uv) + x^3(uv)^2 + \cdots\bigr) = u + x u^2v + x^3 u^3v^2 + \cdots,\ uvx F(u,vx) &= uvx\bigl(1 + x u(vx) + x^3 u^2(vx)^2 + \cdots\bigr) = uvx + x^3 u^2v^2 + x^6 u^3v^3 + \cdots. \end{aligned} ] Summing (1 + uF(ux,vx^{-1}) - uC(x,uv) + uvx F(u,vx)) cancels the (u) and (x u^2v) etc. terms and leaves exactly [ 1 + x,uv + x^3 u^2v^2 + x^6 u^3v^3 + \cdots = F(u,v). ] The functional equation (★) is therefore correct. ∎

Notes

The product formula of Exercise 46(d), [ C(x,z)C(x,xz)\cdots C(x,x^r z) = \sum_{p=0}^\infty C_{p,,p+r}(x),z^p, ] is another consequence of the bivariate recurrence; it can be obtained by iterating (★) or by a direct combinatorial argument. The present derivation makes the generalization of the original identity (27) completely explicit.