A Note on a One-Parameter Family of Catalan-Like Numbers

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract We study a family of sequences of Catalan-like numbers based on the series reversion process. Properties of these sequences are derived, including continued fraction expansions, associated orthogonal polynomials and associated Aigner matrices, which turn out to be Riordan arrays.

1 Introduction

The purpose of this note is to explore some properties of the family of sequences obtained by reverting the expression

\frac{x(1 + rx)}{1 + 2rx + r(r + 1)x^{2}}

where r is an integer parameter. The analysis involves elements of the theory of Riordan arrays [15], orthogonal polynomials [5, 10], continued fractions [18], the Deleham construction (see \underline{A084938}) and Hankel transforms [13]. The overall context of this note is that of “Catalan-like” numbers, a notion defined and developed by Martin Aigner [1, 2]. See also [8, 9, 20]. In the sequel, [x^{n}] denotes the operator that extracts the coefficient of x^{n} in a power series, Rev denotes the operation of reverting a sequence (thus f̄(x) = Revf(x) satisfies f(f̄(x)) = x), [P] is the Iverson operator [11] equal to 0 if P is false, and 1 if P is true, and

c(x) = \frac{1 − \sqrt{1 − 4x}}{2x} = \frac{1}{1 − \frac{x}{1 − \frac{x}{1 − \frac{x}{1 − ⋯}}}}

is the g.f. of the Catalan numbers \underline{A000108}. In addition, (g, f) will denote a Riordan array whose k-th column has generating function g(x)f(x)^{k}. In the next section, we shall provide an introduction to the Riordan group. We recall that a number sequence a_{n} is “Catalan-like” if none of the Hankel determinants |a_{i+j}|_{i,j=0}^{n} is zero, while a lower-triangular matrix (a_{n,k}) is called an Aigner matrix if there exist two sequences s_{n} and t_{n} such that

a_{0,0} = 1, a_{0,k} = 0 (k > 0)

and

a_{n,k} = a_{n−1,k−1} + s_{k}a_{n−1,k} + t_{k+1}a_{n−1,k+1} (n, k ≥ 1).

The (integer) Hankel transform of the sequence a_{n} is the sequence h_{n} with general term

h_{n} = |a_{i+j}|_{i,j=0}^{n}.

2 The Riordan group

The Riordan group [15], [17], is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions g(x) = 1 + g_{1}x + g_{2}x^{2} + … and f(x) = f_{1}x + f_{2}x^{2} + … where f_{1} ≠ 0 [17]. The associated matrix is the matrix whose i-th column is generated by g(x)f(x)^{i} (the first column being indexed by 0). The matrix corresponding to the pair g, f is denoted by (g, f) or R(g, f). The group law is then given by

(g, f) ∗ (h, l) = (g(h ∘ f), l ∘ f).

The identity for this law is I = (1, x) and the inverse of (g, f) is (g, f)^{−1} = (1/(g ∘ f̄), f̄) where f̄ is the compositional inverse of f.

A Riordan array of the form (g(x), x), where g(x) is the generating function of the sequence a_{n}, is called the sequence array of the sequence a_{n}. Its general term is a_{n−k}. Such arrays are also called Appell arrays as they form the elements of the Appell subgroup.

If M is the matrix (g, f), and a = (a_{0}, a_{1}, …)′ is an integer sequence with ordinary generating function A (x), then the sequence Ma has ordinary generating function g(x)A(f(x)). The (infinite) matrix (g, f) can thus be considered to act on the ring of integer sequences Z^{N} by multiplication, where a sequence is regarded as a (infinite) column vector. We can extend this action to the ring of power series Z[[x]] by

(g, f) : A(x) ⟶ (g, f) · A(x) = g(x)A(f(x)).

Example 1. The binomial matrix B is the element (\frac{1}{1−x}, \frac{x}{1−x}) of the Riordan group. It has general element \binom{n}{k}. More generally, B^{m} is the element (\frac{1}{1−mx}, \frac{x}{1−mx}) of the Riordan group, with general term \binom{n}{k}m^{n−k}. It is easy to show that the inverse B^{−m} of B^{m} is given by (\frac{1}{1+mx}, \frac{x}{1+mx}).

The row sums of the matrix (g, f) have generating function

(g, f) · \frac{1}{1 − x} = \frac{g(x)}{1 − f(x)}

while the diagonal sums of (g, f) (sums of left-to-right diagonals in the North East direction) have generating function g(x)/(1 − xf(x)). These coincide with the row sums of the “generalized” Riordan array (g, xf).i

The bi-variate generating function of the Riordan array (g, f) is given by \frac{g(x)}{1−yf(x)}.

3 The sequences a_{n}(r)

The reversion of the function

\frac{x(1 + rx)}{1 + 2rx + r(r + 1)x}

is obtained by solving the equation

\frac{u(1 + ru)}{1 + 2ru + r(r + 1)u} = x

for the unknown u. We obtain

u = \frac{\sqrt{1 − 4rx^{2}} + 2rx − 1}{2r(1 − (r + 1)x)}.

We now define

a_{n}(r) = [x^{n+1}]Rev\frac{x(1 + rx)}{1 + 2rx + r(r + 1)x^{2}}
= [x^{n+1}]\frac{\sqrt{1 − 4rx^{2}} + 2rx − 1}{2r(1 − (r + 1)x)}
= [x^{n}]\frac{\sqrt{1 − 4rx^{2}} + 2rx − 1}{2xr(1 − (r + 1)x)}
= [x^{n}]\frac{c(rx^{2})}{1 − rxc(rx^{2})}
= [x^{n}](c(rx^{2}), rxc(rx^{2})) · \frac{1}{1 − x}
= [x^{n}](c(rx^{2}), xc(rx^{2})) · \frac{1}{1 − rx}
= ∑_{k=0}^{n} \frac{k + 1}{n + k + 2}\binom{n}{\frac{n−k}{2}}(1 + (−1)^{n−k})r^{\frac{n−k}{2}} r^{k}

= ∑_{k=0}^{n} \frac{k + 1}{n + k + 2}\binom{n}{\frac{n−k}{2}}(1 + (−1)^{n−k})r^{\frac{n+k}{2}}

= ∑_{k=0}^{n}[n ≤ 2k]\binom{n}{k}\frac{2k − n + 1}{k + 1}r^{k}.

The final equalities above follow from the fact that the general term of the Riordan array

(c(rx^{2}), xc(rx^{2}))

is given by

\frac{k + 1}{n + k + 2}\binom{n}{\frac{n−k}{2}}(1 + (−1)^{n−k})r^{\frac{n−k}{2}} .

A short table of these sequences is given below.

r A-number Reversion of
1 \underline{A001405}  \frac{x(1+x)}{1+2x+2x^{2}}
2 \underline{A151281}  \frac{x(1+2x)}{1+4x+6x^{2}}
3 \underline{A151162}  \frac{x(1+3x)}{1+6x+12x^{2}}
4 \underline{A151254}  \frac{x(1+4x)}{1+8x+20x^{2}}
5 \underline{A156195} \frac{x(1+5x)}{1+10x+30x^{2}}
6 \underline{A156361} \frac{x(1+6x)}{1+12x+42x^{2}}

For example, a_{n}(1) is the sequence of central binomial numbers \binom{n}{⌊ \frac{n}{2} ⌋}, while a_{n}(3) counts the number of walks within N^{3} (the first octant of Z^{3}) starting at (0, 0, 0) and consisting of n steps taken from {(−1, 0, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0)} [3].

4 Continued fractions

We have

\frac{c(rx^{2})}{1 − rxc(rx^{2})} = \frac{1}{\frac{1}{c(rx^{2})} − rx}
= \frac{1}{1 − rx + (\frac{1}{c(rx^{2})} − 1)}
= \frac{1}{1 − rx + \frac{1−c(rx^{2})}{c(rx^{2})}}

= \frac{1}{1 − rx − rx^{2}c(rx^{2})}
= \frac{1}{1 − rx − \frac{rx^{2}}{1 − \frac{rx^{2}}{1 − \frac{rx^{2}}{1 − ⋯}}}}.

Thus the generating function of a_{n}(r) is given by the continued fraction above. An immediate consequence of this is that a_{n}(r) has Hankel transform r^{\binom{n+1}{2}} [12, 18]. This proves that these numbers are “Catalan-like” (r ≠ 0). We note that the above implies that the bi-variate generating function of the Riordan array

(c(rx^{2}), xc(rx^{2}))

is given by

\frac{1}{1 − xy − \frac{rx^{2}}{1 − \frac{rx^{2}}{1 − \frac{rx^{2}}{1 − ⋯}}}}

while that of the generalized Riordan array

(c(rx^{2}), rxc(rx^{2}))

is given by

\frac{1}{1 − rxy − \frac{rx^{2}}{1 − \frac{rx^{2}}{1 − \frac{rx^{2}}{1 − ⋯}}}}.

There is another link to continued fractions, via the Deleham construction. For the purposes of this note, we define this as follows. Given two sequences r_{n} and s_{n},we use the notation

r Δ s = [r_{0}, r_{1}, r_{2}, …] Δ [s_{0}, s_{1}, s_{2}, …]

to denote the number triangle whose bi-variate generating function is given by

\frac{1}{1 − \frac{(r_{0}x + s_{0}xy)}{1 − \frac{(r_{1}x + s_{1}xy)}{1 − \frac{(r_{2}x + s_{2}xy)}{1 − ⋯}}}}.

In this instance, we follow Deleham in \underline{A120730} by taking r_{n} to be the sequence that begins

0, 1, −1, 0, 0, 1, −1, 0, 0, 1, −1, 0, …

and s_{n} to be the sequence that begins

1, 0, 0, −1, 1, 0, 0, −1, 1, 0, 0, −1, 1, 0, …

(extending periodically). We thus arrive at the number triangle with bi-variate generating function

\frac{1}{1 − \frac{xy}{1 − \frac{x}{1 + \frac{x}{1 + \frac{xy}{1 − \frac{xy}{1 − \frac{x}{1 + \frac{x}{1 + \frac{xy}{1 − ⋯}}}}}}}}}.

This is the triangle with general term

[n ≤ 2k]\binom{n}{k}\frac{2k − n + 1}{k + 1}.

A consequence of the fact that

a_{n}(r) = ∑_{k=0}^{n}[n ≤ 2k]\binom{n}{k}\frac{2k − n + 1}{k + 1}r^{k}

is that the generating function of a_{n}(r) may also be expressed as

\frac{1}{1 − \frac{rx}{1 − \frac{x}{1 + \frac{x}{1 + \frac{rx}{1 − \frac{rx}{1 − \frac{x}{1 + \frac{x}{1 + \frac{rx}{1 − ⋯}}}}}}}}}.

For example, the generating function of the central binomial numbers \binom{n}{⌊ \frac{n}{2} ⌋} can be expressed as

\frac{1}{1 − \frac{x}{1 − \frac{x}{1 + \frac{x}{1 + \frac{x}{1 − \frac{x}{1 − \frac{x}{1 + \frac{x}{1 + \frac{x}{1 − ⋯}}}}}}}}} = \frac{1}{1 − x − \frac{x^{2}}{1 − \frac{x^{2}}{1 − \frac{x^{2}}{1 − ⋯}}}}.

Similarly the generating function of the sequence with g.f. given by \frac{c(2x^{2}}{1−2xc(2x^{2})}, or \underline{A151281} (the number of walks within N^{2} (the first quadrant of Z^{2}) starting at (0, 0) and consisting of n steps taken from {(−1, 0), (1, 0), (1, 1)}), can be expressed as a continued fraction as follows :

\frac{1}{1 − \frac{2x}{1 − \frac{x}{1 + \frac{x}{1 + \frac{2x}{1 − \frac{2x}{1 − \frac{x}{1 + \frac{x}{1 + \frac{2x}{1 − ⋯}}}}}}}}} = \frac{1}{1 − 2x − \frac{2x^{2}}{1 − \frac{2x^{2}}{1 − \frac{2x^{2}}{1 − ⋯}}}}.

5 LDL^{t} decomposition and orthogonal polynomials

We let H = H(r) denote the Hankel matrix of the sequence a_{n}(r), with general element a_{i+j}(r). The theory of “Catalan-like” numbers ensures us that

H = LDL^{t}

where D is a diagonal matrix, and L = L(r) is a lower-triangular matrix with 1’s on the diagonal. Moreover, L^{−1} is the coefficient array of a family of orthogonal polynomials [14, 19]. Given that the Hankel transform of a_{n}(r) is r^{\binom{n+1}{2}}, it is clear from the theory that in fact

D = Diag{1, r, r^{2}, r^{3}, …}.

We obtain

L = (\frac{c(rx^{2})}{1 − rxc(rx^{2})}, xc(rx^{2})) ,

and

L^{−1} = (\frac{1 − rx}{1 + rx^{2}} , \frac{x}{1 + rx^{2}} ) .

This latter matrix has general term

(−r)^{⌊ \frac{n−k+1}{2} ⌋}\binom{n − ⌊\frac{n−k+1}{2}⌋}{⌊\frac{n−k}{2}⌋}.

The matrix L^{−1} is the coefficient array of a set of generalized Chebyshev polynomials of the third kind. To see this, we first let

U_{n}(x; r) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}(−r)^{k}(2x)^{n−2k}.

U_{n}(x; 1) corresponds to the usual Chebyshev polynomials of the second kind. The family of polynomials

U_{n}(x/2; r)

has coefficient array

(\frac{1}{1 + rx^{2}} , \frac{x}{1 + rx^{2}} ) .

The generalized Chebyshev polynomials of the third kind can then be defined to be

V_{n}(x; r) = U_{n}(x; r) − rU_{n−1}(x; r).

(Again, r = 1 corresponds to the usual Chebyshev polynomials of the third kind [4]). Then L^{−1} is the coefficient array of the orthogonal polynomials V_{n}(x/2; r). We can easily verify that these polynomials satisfy the three-term recurrence

V_{n+2}(x/2; r) = xV_{n+1}(x/2; r) − rV_{n}(x/2; r).

Example 2. We take the case r=3. Then we get

L(3) = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 3 & 1 & 0 & 0 & 0 & 0 & … \\ 12 & 3 & 1 & 0 & 0 & 0 & … \\ 45 & 15 & 3 & 1 & 0 & 0 & … \\ 180 & 54 & 18 & 3 & 1 & 0 & … \\ 702 & 234 & 63 & 21 & 3 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

and

L(3)^{−1} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ −3 & 1 & 0 & 0 & 0 & 0 & … \\ −3 & −3 & 1 & 0 & 0 & 0 & … \\ 9 & −6 & −3 & 1 & 0 & 0 & … \\ 9 & 18 & −9 & −3 & 1 & 0 & … \\ −27 & 27 & 27 & −12 & −3 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

L(3) is an Aigner matrix for the sequences 3, 0, 0, 0, … and 3, 3, 3, . . .. Thus for instance

702 = 3 · 180 + 3 · 54, 234 = 180 + 3 · 18.

The generalized Chebyshev polynomials of the third kind associated to a_{n}(3) begin 1, x − 3, x^{2} − 3x − 3, x^{3} − 3x^{2} − 6x − 9, …

6 Moment representation

By means of the Stieltjes transform [10], we can establish that

a_{n}(r) = \frac{1}{2π} ∫_{−2\sqrt{r}}^{2\sqrt{r}} x^{n} \frac{\sqrt{4r − x^{2}}}{r(r + 1 − x)}dx + \frac{r − 1}{r}(r + 1)^{n}.

7 Production matrices

It is instructive to examine the production matrices [6, 7] of some of the Riordan arrays involved in this note. The Riordan array

(c(rx^{2}), xc(rx^{2}))

has production matrix

( \begin{matrix}0 & 1 & 0 & 0 & 0 & 0 & … \\ r & 0 & 1 & 0 & 0 & 0 & … \\ 0 & r & 0 & 1 & 0 & 0 & … \\ 0 & 0 & r & 0 & 1 & 0 & … \\ 0 & 0 & 0 & r & 0 & 1 & … \\ 0 & 0 & 0 & 0 & r & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

while the generalized Riordan array

(c(rx^{2}), rxc(rx^{2}))

has production matrix

( \begin{matrix}0 & r & 0 & 0 & 0 & 0 & … \\ 1 & 0 & r & 0 & 0 & 0 & … \\ 0 & 1 & 0 & r & 0 & 0 & … \\ 0 & 0 & 1 & 0 & r & 0 & … \\ 0 & 0 & 0 & 1 & 0 & r & … \\ 0 & 0 & 0 & 0 & 1 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The Riordan array

L = (\frac{c(rx^{2})}{1 − rxc(rx^{2})}, xc(rx^{2}))

has production matrix

( \begin{matrix}r & 1 & 0 & 0 & 0 & 0 & … \\ r & 0 & 1 & 0 & 0 & 0 & … \\ 0 & r & 0 & 1 & 0 & 0 & … \\ 0 & 0 & r & 0 & 1 & 0 & … \\ 0 & 0 & 0 & r & 0 & 1 & … \\ 0 & 0 & 0 & 0 & r & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

which confirms that its first column, which is a_{n}(r), has generating function given by the continued fraction

\frac{1}{1 − rx − \frac{rx^{2}}{1 − \frac{rx^{2}}{1 − ⋯}}}.

L is thus the Aigner matrix for the sequences s_{n} given by r, 0, 0, 0, … and t_{n} given by r, r, r, . . ..

8 a_{n}(r) as row sums

Following [9], it is possible to exhibit the sequences a_{n}(r) as the row sums of a given number triangle. In effect, the matrix LB^{−1}, where B is the Binomial matrix with general term \binom{n}{k} (Pascal’s triangle, \underline{A007318}), has row sums equal to a_{n}(r). This matrix is the inverse of

(\frac{1}{1 − x}, \frac{x}{1 − x}) · (\frac{1 − rx}{1 + rx^{2}} , \frac{x}{1 + rx^{2}} ) = (\frac{1 − (r + 1)x}{1 − 2x + (r + 1)x^{2}} , \frac{x(1 − x)}{1 − 2x + (r + 1)x^{2}} ) .

We may verify this algebraically: the row sums of

LB^{−1} = (\frac{c(rx^{2})}{1 − rxc(rx^{2})} \frac{1}{1 + xc(rx^{2})}, \frac{xc(rx^{2})}{1 + xc(rx^{2})})

do have generating function \frac{c(rx^{2})}{1−rxc(rx^{2})}.

References

[1] M. Aigner, Catalan-like numbers and determinants, J. Combin. Theory Ser. A 87 (1999), 33–51.

[2] M. Aigner, Catalan and other numbers: a recurrent theme, in: H. Crapo and D. Senato, eds., Algebraic Combinatorics and Computer Science, Springer Italia, Milan, 2001, pp. 347–390.

[3] A. Bostan and M. Kauers, Automatic classification of restricted lattice walks, arXiv:0811.2899v1. Available electronically at http://arxiv.org/abs/0811.2899 .

[4] L. Boyadjiev and R. Scherer, On the Chebyshev polynomials, Kuwait J. Sci. Engrg. 28 (2001), 227–239.

[5] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, New York, 1978.

[6] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices, Adv. in Appl. Math 34 (2005), 101–122.

[7] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices and Riordan arrays,

http://arxiv.org/abs/math/0702638v1 .

[8] L. Ferrari, E. Pergola, R. Pinzani and S. Rinaldi, Some applications arising from the interactions between the theory of Catalan-like numbers and the ECO method, available

electronically at http://www.dsi.unifi.it/~ferrari/applecoadm.pdf

[9] L. Ferrari and R. Pinzani, Catalan-like numbers and succession rules, Pure Math. Appl. 16 (2005), 229–250.

[10] W. Gautschi, Orthogonal Polynomials: Computation and Approximation, Clarendon Press, Oxford, 2003.

[11] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2e, Addison-Wesley, 1994.

[12] C. Krattenthaler, Advanced determinant calculus, math.CO/9902004. Available elec-

tronically at http://arxiv.org/abs/math/9902004

[13] J. W. Layman, The Hankel transform and some of its properties, J. Integer Seq. 4 (2001), Article 01.1.5.

[14] P. Peart and W-J. Woan, Generating functions via Hankel and Stieltjes matrices, J. Integer Seq. 3 (2000), Article 00.2.1.

[15] L. W. Shapiro, S. Getu, W-J. Woan and L.C. Woodson, The Riordan group, Discr. Appl. Math. 34 (1991) 229–239.

[16] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electroni-

   cally at http://www.research.att.com/∼njas/sequences/.

[17] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

[18] H. S. Wall, Analytic Theory of Continued Fractions, AMS Chelsea Publishing, 2000.

[19] W-J. Woan, Hankel matrices and lattice paths, J. Integer Seq. 4 (2001), Article 01.1.2.

[20] Zhizheng Zhang, A characterization of Aigner-Catalan-like numbers, Indian J Pure Appl. Math. 32 (2001), 1615–1619.

2000 Mathematics Subject Classification: Primary 11B83; Secondary 11Y55, 42C05. Keywords: Integer sequence, Catalan-like, Riordan arrays, Hankel transform, orthogonal polynomials, Chebyshev polynomials.

(Concerned with sequences \underline{A000108},\underline{A001405}, \underline{A007318}, \underline{A084938}, \underline{A120730}, \underline{A151281}, \underline{A151162}, \underline{A151254}, \underline{A156195}, and \underline{A156361}.)

Received March 11 2009; revised version received June 6 2009. Published in Journal of Integer Sequences, June 6 2009.

Return to Journal of Integer Sequences home page.