The Super Patalan Numbers

Thomas M. Richardson 3438 N. Applecrest Ct., SE Ada, MI 49301 USA

                        ribby@umich.edu

Abstract We introduce the super Patalan numbers, a generalization of the super Catalan numbers in the sense of Gessel, and prove a number of properties analogous to those of the super Catalan numbers. The super Patalan numbers generalize the super Catalan numbers similarly to how the Patalan numbers generalize the Catalan numbers.

1 Introduction

We introduce the super Patalan numbers as a generalization of the super Catalan numbers. The super Catalan numbers (sequence \underline{A068555} in the On-Line Encyclopedia of Integer Sequences [6]) were studied by Gessel in his paper on the super ballot numbers [2]. (The term super Catalan numbers is also used to refer to a different sequence. We are generalizing the term as used by Gessel.) Just as the super Catalan numbers form a two-dimensional array that extends the Catalan numbers, the super Patalan numbers of order p form a two-dimensional array that extends the Patalan numbers of order p.

The super Patalan numbers have a number of properties that generalize the corresponding properties of the super Catalan numbers, in particular Eqs. (5), (7), (9), and (10). We also prove that the super Patalan numbers are integers, and we give a convolutional recurrence for the Patalan numbers, that generalizes the well known recurrence for the Catalan numbers.

We start with the definitions of the super Catalan numbers and of the Patalan numbers.

Definition 1. Define the super Catalan numbers S(m, n) by

S(m, n) = \frac{(2m)!(2n)!}{m!n!(m + n)!}.

The Catalan numbers C_{n} are contained in the super Catalan numbers as 2C_{n} = S(n, 1) = \frac{2(2n)!}{n!(n+1)!}.

Definition 2. Let p be a positive integer with p > 1, and let q be a positive integer with q < p. Define the Patalan numbers of order p to be the sequence a(n) with

a(n) = −p^{2n+1}\binom{n − 1/p}{n + 1}.  (1)

Also define the (p, q)-Patalan numbers to be the sequence b(n) with

b(n) = −p^{2n+1}\binom{n − q/p}{n + 1}.  (2)

The Patalan numbers of order p (see sequences \underline{A025748} – \underline{A025757}) generalize the Catalan numbers. In particular the Catalan numbers are the Patalan numbers of order 2. It can also be seen that the generating function of the Patalan numbers of order p generalizes the generating function of the Catalan numbers. The generating function of the Patalan numbers of order p is

\frac{1 − (1 − p^{2}x)^{1/p}}{px} ,  (3)

and the generating function for the (p, q)-Patalan numbers is

\frac{1 − (1 − p^{2}x)^{q/p}}{px} .  (4)

The formula for the generating function of the (p, q)-Patalan numbers can be seen easily using (2) and the binomial coefficient identity

\binom{n − q/p}{n + 1} = (−1)^{n+1}\binom{q/p}{n + 1}.

Now we define the super Patalan numbers as an extension of the Patalan numbers, and generalizing the super Catalan numbers.

Definition 3. Define the sequence Q(i, j) of (p, q)-super Patalan numbers by

Q(i, j) = (−1)^{j}p^{2(i+j)}\binom{i − q/p}{i + j}.  (5)

Let P (i, j), the super Patalan numbers of order p, be the (p, q)-super Patalan numbers with q = 1.

The super Patalan numbers do not have quite as simple an expression as the super Catalan numbers. In particular, they do not form a symmetric array (see sequences \underline{A248324}, \underline{A248325}, \underline{A248326}, \underline{A248328}, \underline{A248329}, \underline{A248332}). While the super Patalan numbers are not symmetric, they do have a twisted symmetry in that the arrays of (p, q)-super Patalan numbers and (p, p − q)-super Patalan numbers are transposes of each other.

Theorem 4. Let Q be the (p, q)-super Patalan numbers, and let Q̃ be the (p, p − q)-super Patalan numbers. Then Q and Q̃ satisfy

Q(i, j) = Q̃(j, i).  (6)

Proof. This follows from the binomial coefficient identity

(−1)^{j}\binom{i − q/p}{i + j} = (−1)^{i}\binom{j + q/p − 1}{i + j}.

The Patalan numbers are contained in the super Patalan numbers just as the Catalan numbers are contained in the super Catalan numbers. If a(n) is the sequence of Patalan numbers of order p, and P (i, j) are the super Patalan numbers of order p, then the Patalan numbers are contained in the super Patalan numbers as

pa(n) = P (n, 1).  (7)

It is the author’s opinion that to be consistent with Eq. (7) concerning column 1 of the super Patalan matrix, the Patalan numbers of order p should start 1, \binom{p}{2} \underline{A097188} and not start 1, 1, \binom{p}{2} \underline{A025748}. The fact that the Catalan numbers start 1, 1 is explained by the Catalan numbers being the Patalan number of order 2, and \binom{2}{2} = 1.

2 Generating functions and extended super Patalan numbers

Eq. (5) generalizes an identity of Gessel [2, unlabelled equation before Eq. (31)]. This indicates that Q(m, n) is the coefficient of x^{m+n} in

(−1)^{m}(1 − p^{2}x)^{m−q/p}.  (8)

More generally, the above definitions may be extended to define super Patalan numbers for all m and n.

Definition 5. Let m, n be integers. Define the extended (p, q)-super Patalan numbers E(m, n) to be the coefficient of x^{m+n} in (−1)^{m}(1 − p^{2}x)^{m−q/p}.

While E is defined in terms of the generating functions of its rows, the twisted symmetry of the super Patalan matrix implies that E(m, n) is also the coefficient of x^{m+n} in (−1)^{n}(1 − p^{2}x)^{n−(p−q)/p}.

The lower triangular matrix L formed by permuting the columns of E, such that L(m, n) = E(m, −n), has the interesting property that it has order 2 under matrix multiplication.

Theorem 6. Let L be the doubly infinite lower triangular matrix given by L(m, n) = E(m, −n), for all integers m and n, where E is an extended super Patalan matrix. Then L^{2} is the identity.

Proof. Since L is lower triangular, the (m, n) entry of L^{2} is equal to 0 for m < n. Since the diagonal entries of L have the values ±1, it follows that the diagonal entries of L^{2} are equal to 1. Consider the (m, n) entry of L^{2} for n < m. The product of row m of L and column n of L is

∑_{k=n}^{m} L(m, k)L(k, n) = ∑_{k=n}^{m} E(m, −k)E(k, −n).

The sum ∑_{k=n}^{m} E(m, −k)E(k, −n) is the coefficient of x^{m−n} in the product of the generating function of row m of E (∑_{k≥−m} E(m, k)x^{m+k}) and the generating function of column −n of E (∑_{k≥n} E(k, −n)x^{k−n}.) Since the generating function of row m of E is (−1)^{m}(1−p^{2}x)^{m−q/p}, and the generating function of column −n of E is (−1)^{−n}(1−p^{2}x)^{−n−(p−q)/p}, this convolution gives us a coefficent of the polynomial (−1)^{m−n}(1 − p^{2}x)^{m−n−1}. Thus the (m, n) entry of L^{2} is the coefficient of x^{m−n} in (−1)^{m−n}(1 − p^{2}x)^{m−n−1}, which equals 0. The completes the proof that L^{2} is the identity.

We will use the following lemma to find the two-variable generating function of Q, as well as in the proof of Theorem 11.

Lemma 7. The (p, q)-super Patalan numbers Q satisfy

p^{2}Q(i, j) = Q(i, j + 1) + Q(i + 1, j).  (9)

Proof.

Q(i, j + 1) + Q(i + 1, j) =(−1)^{j+1}p^{2i+2j+2}\binom{i − q/p}{i + j + 1}

+ (−1)^{j}p^{2i+2j+2}\binom{i + 1 − q/p}{i + j + 1}

=(−1)^{j}p^{2i+2j+2}(\binom{i + 1 − q/p}{i + j + 1} − \binom{i − q/p}{i + j + 1})

=(−1)^{j}p^{2i+2j+2}(\binom{i − q/p}{i + j})
=p^{2}Q(i, j).

Next we consider the two-variable generating function of Q.

Theorem 8. Let F (x, y) = ∑ Q(i, j)x^{i}y^{j} be the generating function of the super Patalan numbers Q(i, j). Then

F (x, y) = (\frac{x}{(1 − p^{2}x)^{(p−q)/p}} + \frac{y}{(1 − p^{2}y)^{q/p}} )\frac{1}{x + y − p^{2}xy} .  (10)

Proof. By (8), the generating function of row i = 0 of the super Patalan matrix of order p is g(y) = ∑_{j≥0} Q(0, j)y^{j} = (1 − p^{2}y)^{−q/p}, and Eq. (6) implies that the generating function of column j = 0 of the super Patalan matrix of order p is f(x) = ∑_{i≥0} Q(i, 0)x^{i} = (1 − p^{2}x)^{−(p−q)/p}.

Eq. (9) implies the equation

p^{2}F (x, y) = \frac{F (x, y) − g(y)}{x} + \frac{F (x, y) − f(x)}{y}.  (11)

Solving Eq. (11) for F (x, y) gives Eq. (10), as required.

Eq. (9) generalizes an identity attributed to D. Rubenstein by Gessel [2, Eq. (36)]. Also, Eq. (10) generalizes a similar expression given by Gessel for the generating function of the super Catalan numbers [2, Eq. (37)].

3 Convolutional Recurrence

The Catalan numbers have a very simple, well known, and interesting convolutional recurrence,

C_{n} = ∑_{k=0}^{n−1} C_{k}C_{n−k−1}.  (12)

We show that the Patalan numbers of order p have a similar convolutional recurrence of degree p, and give the explicit recurrence for the Patalan numbers of order 3.

We work directly with the generating function of the Patalan numbers. Let A(x) be the

generating function of the Patalan numbers of order p, so that A(x) = \frac{1 − (1 − p^{2}x)^{1/p}}{px}.

Gessel observed that for p = 3, xA(x) is the compositional inverse of x − 3x^{2} + 3x^{3} \underline{A097188}.

More generally, xA(x) is the compositional inverse of \frac{1 − (1 − px)^{p}}{p^{2}} = − ∑_{k=1}^{p} \binom{p}{k}p^{k−2}(−x)^{k}.

Composing the compositional inverse with xA(x) gives the equation

x = − ∑_{k=1}^{p} \binom{p}{k}p^{k−2}(−xA(x))^{k}.  (13)

For degree n > 1, the left hand side of (13) is equal to 0. Setting 0 equal to the degree n term of the right hand side of Eq. (13) gives

0 = − ∑_{k=1}^{p} \binom{p}{k}p^{k−2} ∑_{i_{1}+...+i_{k}=n} ∏_{j=1}^{k} a(i_{j} − 1)(−1)^{k}x^{n}.

Solving for the term with k = 1 gives

a(n − 1)x^{n} = ∑_{k=2}^{p} \binom{p}{k}p^{k−2} ∑_{i_{1}+...+i_{k}=n} ∏_{j=1}^{k} a(i_{j} − 1)(−1)^{k}x^{n}.

Shifting indices and equating the coefficients gives

a(n) = ∑_{k=2}^{p} \binom{p}{k}p^{k−2}(−1)^{k} ∑_{i_{1}+...+i_{k}=n−k+1} ∏_{j=1}^{k} a(i_{j}).  (14)

Because we are working with the compositional inverse of xA(x), not of A(x), the sum of the indices of each term on the right hand side of (14) is less than the index of the left hand side by one less than the number of factors in the term.

It is easily verified that for p = 2, Eq. (14) reduces to Eq. (12). For p = 3, Eq. (14) reduces to

a(n) = ∑_{k=0}^{n−1} 3a(k)a(n − k − 1) − ∑_{i+j+k=n−2} 3a(i)a(j)a(k).  (15)

Eq. (14) for n = 1 has only one non-trivial term on the right hand side, and it implies that a(1) = \binom{p}{2}.

4 The super Patalan numbers are integers

Lang proved that the Patalan numbers are integers [4, Note 4, Lemma 19]. We give an alternate proof that the Patalan numbers are integers, and we also prove that the super Patalan numbers are integers.

Theorem 9. The Patalan numbers of order p are integers.

Proof. Let p > 1 be an integer and let a(n) be the sequence of Patalan numbers of order p. By the definition a(0) = 1 and Eq. (14), it follows that a(n) is an integer for all n ≥ 0.

Theorem 10. The (p, q)-Patalan numbers are integers.

Proof. By Eq. (3), the generating function of the Patalan numbers of order p is f(x) = \frac{1−(1−p^{2}x)^{1/p}}{px}, and from Eq. (4), the generating function of the (p, q)-Patalan numbers is g(x) =

\frac{1−(1−p^{2}x)^{q/p}}{px}. It follows that g(x) = \frac{1−(1−pxf(x))^{q}}{px}, and so g(x) = ∑_{k=1}^{q}(−1)^{k+1}\binom{q}{k}(pxf(x))^{k}. Thus the (p, q)-Patalan numbers may be expressed as an integral linear combination of the k^{th} convolution powers of the Patalan numbers of order p, for 1 ≤ k ≤ q, and thus they are integers.

Theorem 11. The (p, q)-super Patalan numbers are integers.

Proof. Let Q(i, j) be the (p, q)-super Patalan numbers. By (7), the super Patalan numbers Q(n, 1) are an integer multiple of the (p, q)-Patalan numbers, so they are integers. Now rewriting (9) as Q(i, j + 1) = p^{2}Q(i, j) − Q(i + 1, j) shows that Q(i, j) is an integer for j > 1. Similarly, since by definition Q(0, 0) = 1, rewriting (9) as Q(i + 1, j) = p^{2}Q(i, j) − Q(i, j + 1) shows that Q(i, 0) is an integer.

5 Factorization of the super Patalan matrix

Definition 12. Define the reciprocal Pascal matrix to be the matrix R with R(i, j) = \binom{i+j}{i}^{−1}.

Lemma 13. Let Q be the (p, q)-super Patalan numbers, let G_{p,q} be the diagonal matrix with G_{p,q}(i, i) = Q(i, 0), and let F_{p,q} be the diagonal matrix with F_{p,q}(i, i) = Q(0, i). Then

Q = G_{p,q}RF_{p,q}.  (16)

Proof. The (i, j) entry of the right hand side is

G_{p,q}(i, i)R(i, j)F_{p,q}(j, j) = \binom{i − q/p}{i}\binom{i + j}{i}^{−1}\binom{−q/p}{j}

= \frac{(i − q/p)!}{i!(−q/p)!} \frac{i!j!}{(i + j)!} \frac{(−q/p)!}{j!(−j − q/p)!}

= \frac{(i − q/p)!}{(i + j)!(−j − q/p)!}

and this last expression is Q(i, j).

The author previously used the factorization of Eq. (16), for the case p = 2, to prove that the inverse of the reciprocal Pascal matrix is an integer matrix [5].

Next we prove that the inverse of the Hadamard inverse of the super Patalan matrix is an integer matrix.

Theorem 14. Let Q be the (p, q)-super Patalan matrix, and let H be the n × n matrix given by H(i, j) = \frac{1}{Q(i,j)} for 0 ≤ i, j < n. Then the inverse of H is an integer matrix.

Proof. Let G(n) and F (n) be the upper left n × n sections of G_{p,q} and F_{p,q}, respectively. Lemma 13, and the fact that G(n) and F (n) are diagonal, show that

H = G(n)^{−1}BF (n)^{−1},

where B is the n × n Pascal matrix with B(i, j) = \binom{i+j}{i}, for 0 ≤ i, j < n. Then

H^{−1} = F (n)B^{−1}G(n).

Since B^{−1}, G(n), and F (n) are all integer matrices, it follows that H^{−1} also is an integer matrix.

References

[1] Emily Allen and Irina Gheorghiciuc, A weighted interpretation for the super Catalan numbers, J. Integer Seq. 17 (2014), Article 14.10.7.

[2] Ira M. Gessel, Super ballot numbers, J. Symbolic Comput. 14 (1992), 179–194.

[3] Ira M. Gessel and Guoce Xin, A combinatorial interpretation of the numbers 6(2n)!/n!(n + 2)!, J. Integer Seq. 8 (2005), Article 05.2.3.

[4] Wolfdieter Lang, Generalizations of the Stirling number triangle, J. Integer Seq. 3 (2000), Article 00.2.4.

[5] Thomas M. Richardson, The reciprocal Pascal matrix, preprint, 2014,

   http://arxiv.org/abs/1405.6315.

[6] N. J. A. Sloane, Online Encyclopedia of Integer Sequences. Published electronically at

   http://oeis.org.

2010 Mathematics Subject Classification: Primary 5A10; Secondary 11B37, 11B75, 15A36. Keywords: Catalan number, Patalan number, super Catalan number, super Patalan number, generating function, Pascal matrix.

(Concerned with sequences \underline{A025748}, \underline{A025749}, \underline{A025750}, \underline{A025751}, \underline{A025752}, \underline{A025753}, \underline{A025754}, \underline{A025755}, \underline{A025756}, \underline{A025757}, \underline{A068555}, \underline{A097188}, \underline{A248324}, \underline{A248325}, \underline{A248326}, \underline{A248328}, \underline{A248329}, and \underline{A248332}.)

Received October 27 2014; revised version received January 27 2015. Published in Journal of Integer Sequences, February 10 2015.

Return to Journal of Integer Sequences home page.