A Combinatorial Proof of the Log-Convexity of Catalan-Like Numbers

Hua Sun and Yi Wang School of Mathematical Sciences Dalian University of Technology Dalian 116024 PR China

                      hanch.sun@gmail.com
                      wangyi@dlut.edu.cn

Abstract

The Catalan-like numbers c_{n,0}, defined by c_{n+1,k} = r_{k−1}c_{n,k−1} + s_{k}c_{n,k} + t_{k+1}c_{n,k+1} for n, k ≥ 0,

c_{0,0} = 1, c_{0,k} = 0 for k ≠ 0,

unify a substantial amount of well-known counting coefficients. Using an algebraic approach, Zhu showed that the sequence (c_{n,0})_{n≥0} is log-convex if r_{k}t_{k+1} ≤ s_{k}s_{k+1} for all k ≥ 0. Here we give a combinatorial proof of this result from the point of view of weighted Motzkin paths.

1 Introduction

A sequence a_{0}, a_{1}, a_{2}, … of nonnegative numbers is called log-convex if a_{n}^{2} ≤ a_{n+1}a_{n−1} for all n ≥ 1. Many well-known combinatorial sequences are log-convex (see Liu and Wang [9] for instance). One of the simplest classes of log-convex sequences, yet still large enough to include many important instance, is the class of the Catalan-like numbers. The Catalan-like numbers c_{n,0}, introduced by Aigner [1, 2], are defined by the recursive system

c_{n+1,k} = r_{k−1}c_{n,k−1} + s_{k}c_{n,k} + t_{k+1}c_{n,k+1} for n, k ≥ 0,  (1)
c_{0,0} = 1, c_{0,k} = 0 for k ≠ 0,

where (r_{n})_{n≥0}, (s_{n})_{n≥0} and (t_{n})_{n≥1} are three sequences of nonnegative numbers. The Catalanlike numbers unify many well-known counting coefficients. For example, let r_{k} ≡ 1, σ = (s_{0}, s_{1}, …) and τ = (t_{1}, t_{2}, …) in (1). Then c_{n,0} are

(1) the Catalan numbers C_{n} if σ = (1, 2, 2, …) and τ = (1, 1, 1, …);

(2) the Motzkin numbers M_{n} if σ = τ = (1, 1, 1, …);

(3) the middle binomial coefficients \binom{2n}{n} if σ = (2, 2, 2, …) and τ = (2, 1, 1, …);

(4) the Schröder numbers S_{n} if σ = (2, 3, 3, …) and τ = (2, 2, 2, …);

(5) the Bell numbers B_{n} if σ = τ = (1, 2, 3, 4, …);

(6) the (restricted) hexagonal numbers H_{n} if σ = (3, 3, 3, …) and τ = (1, 1, 1, …);

(7) the Fine numbers F_{n} if σ = (0, 2, 2, …) and τ = (1, 1, 1, …);

(8) the Riordan numbers R_{n} if σ = (0, 1, 1, …) and τ = (1, 1, 1, …).

Recently, Zhu [14] established the following criterion for the log-convexity of the Catalanlike numbers.

Theorem 1. ([14, Theorem 3.1]) Assume that r_{k}t_{k+1} ≤ s_{k}s_{k+1} for all k ≥ 0. Then the sequence (c_{n,0})_{n≥0} defined recursively by (1) is log-convex.

Theorem 1 leads to the log-convexity of many well-known combinatorial sequences, including the Catalan numbers, the Motzkin numbers, the Bell numbers, the middle binomial coefficients, the (restricted) hexagonal numbers, the Schröder numbers, and so on (see [14] for details). On the other hand, Callan [3] gave an injective proof for the log-convexity of the Motzkin numbers. Liu and Wang [9] did the same for the Catalan numbers, and asked for a combinatorial proof for the log-convexity of the Bell numbers. The object of the present paper is to give a combinatorial proof for Theorem 1 from the point of view of weighted Motzkin paths.

A Motzkin path of length n is a lattice path from (0, 0) to (n, 0) consisting of up steps U = (1, 1), down steps D = (1, −1) and horizontal steps H = (1, 0) that never falls below the x-axis. The height of a step in a Motzkin path is the y coordinate of the starting point. We assign a weight r_{k} (s_{k}, t_{k}, resp.) to all up steps (all horizontal steps, all down steps, resp.) of height k. Define the weight of a Motzkin path to be the product of weights of its steps. Similarly, we may define a general Motzkin path from (0, 0) to (n, k) for n ≥ k (see [7] for instance). Then c_{n,k} defined by (1) is the sum of weights of all paths from (0, 0) to (n, k). In particular, the Catalan-like number

c_{n,0} = ∑_{P ∈M_{n}} w(P),  (2)

where M_{n} denotes the set of the Motzkin paths of length n [2].

In the next section we give a combinatorial proof of Theorem 1 by means of (2). In Section 3 we point out that the same idea may be applied to show the q-version of Theorem 1. We also propose a couple of problems.

2 Combinatorial proof of Theorem 1

To show the log-convexity of the sequence (c_{n,0})_{n≥0}, it suffices to show that

∑_{P ∈M_{n}} w(P) ∑_{P ∈M_{n}} w(P) ≤ ∑_{P ∈M_{n+1}} w(P) ∑_{P ∈M_{n−1}} w(P),

or equivalently,

∑_{(P_{1},P_{2})∈(M_{n},M_{n})} w(P_{1}, P_{2}) ≤ ∑_{(P′_{1},P′_{2})∈(M_{n+1},M_{n−1})} w(P′_{1}, P′_{2}),  (3)

where w(Q_{1}, Q_{2}) = w(Q_{1})w(Q_{2}) denotes the weight of a pair of paths (Q_{1}, Q_{2}). Let S be a set of pairs of paths. Denote

w(S) = ∑_{(Q_{1},Q_{2})∈S} w(Q_{1}, Q_{2}).

Then (3) is equivalent to

w(M_{n}, M_{n}) ≤ w(M_{n+1}, M_{n−1}).  (4)

Recall that the Motzkin number M_{n} is precisely the Catalan-like number c_{n,0} when the all weights r_{k}, s_{k}, t_{k} equal to 1. In other words, M_{n} counts the Motzkin paths of length n. Callan [3] proved the log-convexity of the Motzkin numbers by establishing an injection from (M_{n}, M_{n}) to (M_{n+1}, M_{n−1}). We rewrite his proof as follows for our purposes.

For each pair of Motzkin paths (Q_{1}, Q_{2}) in (M_{n}, M_{n}) or (M_{n+1}, M_{n−1}), place the first beginning from (0, 0) and the second beginning from (1, 0). Callan introduced the following operation on (Q_{1}, Q_{2}) at each possible “close encounter” to obtain a new pair of Motzkin paths.

1. Assume that Q_{1} and Q_{2} intersect at a lattice point. Then reassign the two initial segments to the other path.

2. Assume that Q_{1} and Q_{2} intersect at the center point of crossing diagonal steps. Then swing the crossing steps 45^{∘} so they become horizontal.

3. Assume that Q_{1} and Q_{2} possess a pair of flatsteps forming the top and bottom of a unit square. Then change the lower horizontal step to an upstep and the upper one to a downstep.

For example, for a pair of Motzkin paths (P_{1}, P_{2}) in (M_{n}, M_{n}), we place P_{1} from (0, 0) to (n, 0) and P_{2} from (1, 0) to (n + 1, 0). Clearly, P_{1} and P_{2} must intersect, so they have at least one close encounter. Callan’s operation at each close encounter of (P_{1}, P_{2}) will lead to a pair of Motzkin paths in (M_{n+1}, M_{n−1}).

[figure: (0, 0); (7, 0); (1, 0); (8, 0); r_{0}; r_{1}; t_{2}; s_{1}; s_{1}; s_{1}; t_{1}; r_{0}; r_{1}; s_{2}; t_{2}; t_{1}; r_{0}; t_{1}]

[figure: (1); (2); (3)]

Figure 1. Callan’s operation on a pair of Motzkin paths.

The above row in Figure 1 is a pair of Motzkin paths of length 7 with one lattice point of intersection, two pairs of crossing steps and one pair of flatsteps. The below low is obtained by carrying out Callan’s operation at the first three close encounters of the pair of Motzkin paths.

Now for (P_{1}, P_{2}) ∈ (M_{n}, M_{n}), let (P′_{1}, P′_{2}) be the pair of paths obtained by carrying out Callan’s operation at the first close encounter of P_{1} and P_{2}. Note that the location of the first close encounter will remain invariant. Hence the mapping

τ : (P_{1}, P_{2}) ↦ (P′_{1}, P′_{2})

is an injection from (M_{n}, M_{n}) to (M_{n+1}, M_{n−1}). This gives a combinatorial interpretation of the log-convexity of the Motzkin numbers.

Note that the inequality w(P_{1}, P_{2}) ≤ w(τ(P_{1}, P_{2})) does not hold in general. For example, if the first close encounter of (P_{1}, P_{2}) is a pair of flatsteps with heights k and k+1 respectively, then τ(P_{1}, P_{2}) is the pair of paths obtained by changing this pair of flatsteps of (P_{1}, P_{2}) to a pair of crossing steps. Thus w(P_{1}, P_{2}) = s_{k}s_{k+1}\overline{w} ≥ r_{k}t_{k+1}\overline{w} = w(τ(P_{1}, P_{2})), where \overline{w} is the product of weights of steps in (P_{1}, P_{2}) except that pair of flatsteps. Hence Callan’s injection τ can not be used to prove the inequality (4). However, we may still prove (4) by means of Callan’s operation.

We divide (M_{n}, M_{n}) into two parts: ℒ consists of pairs of paths that there is at least one lattice point of intersection and 𝒞 consists of the remain pairs. Let (M_{n+1}, M_{n−1})^{∗} consist of pairs of paths in (M_{n+1}, M_{n−1}) that there is at least one close encounter and divide (M_{n+1}, M_{n−1})^{∗} into two parts ℒ^{∗} and 𝒞^{∗} similarly. We show the inequality (4) by showing that

w(ℒ) = w(ℒ^{∗})  (5)

and

w(𝒞) ≤ w(𝒞^{∗}).  (6)

Consider a pair of paths (P_{1}, P_{2}) ∈ ℒ. Let p be their first lattice point of intersection. Assume that p splits P_{1} into parts P_{11} and P_{12}, and splits P_{2} into parts P_{21} and P_{22}. Then the concatenation P_{1}^{∗} of P_{11} and P_{22} is a path of length n + 1, and the concatenation P_{2}^{∗} of P_{12} and P_{21} is a path of length n − 1. Clearly, (P_{1}^{∗}, P_{2}^{∗}) ∈ ℒ^{∗} and p is also their first lattice point of intersection. Furthermore,

w(P_{1}^{∗}, P_{2}^{∗}) = w(P_{11})w(P_{22})w(P_{12})w(P_{21}) = w(P_{1}, P_{2}).

So the mapping

τ^{∗} : (P_{1}, P_{2}) ↦ (P_{1}^{∗}, P_{2}^{∗})

is a weight-preserving bijection from ℒ to ℒ^{∗}. Thus the equality (5) follows.

It remains to show that the inequality (6) holds. Let (P_{1}, P_{2}) ∈ 𝒞. Then each close encounter of (P_{1}, P_{2}) is a pair of crossing steps or a pair of flatsteps. Define the height of such a close encounter as the smaller of heights of two corresponding steps. Callan’s operation changes a pair of crossing steps to a pair of flatsetps of the same height, and vice versa. If (P′_{1}, P′_{2}) is obtained by carrying out Callan’s operation on (P_{1}, P_{2}) at a pair crossing steps of height k, then w(P_{1}, P_{2}) = s_{k}s_{k+1}\overline{w} and w(P′_{1}, P′_{2}) = r_{k}t_{k+1}\overline{w}, where \overline{w} is the product of weights of steps in (P_{1}, P_{2}) except that pair of crossing steps, and vice versa.

Denote by O(P_{1}, P_{2}) and E(P_{1}, P_{2}) the sets of pairs of paths obtained by carrying out Callan’s operation on (P_{1}, P_{2}) at odd and even close encounters respectively. Then O(P_{1}, P_{2}) ⊆ (M_{n+1}, M_{n−1}) and E(P_{1}, P_{2}) ⊆ (M_{n}, M_{n}). Let {i_{1}, i_{2}, …, i_{m}} be the set of heights of close encounters of (P_{1}, P_{2}). Note that each pair of paths in O(P_{1}, P_{2}) and E(P_{1}, P_{2}) has even and odd pairs of crossing steps respectively. Hence

w(O(P_{1}, P_{2})) − w(E(P_{1}, P_{2})) = ∑_{(Q_{1},Q_{2})∈O(P_{1},P_{2})} w(Q_{1}, Q_{2}) − ∑_{(Q′_{1},Q′_{2})∈E(P_{1},P_{2})} w(Q′_{1}, Q′_{2})
= (S_{i_{1}} − R_{i_{1}})(S_{i_{2}} − R_{i_{2}}) ⋯ (S_{i_{m}} − R_{i_{m}})W,

where R_{k} = r_{k}t_{k+1}, S_{k} = s_{k}s_{k+1} and W is the product of weights of steps in (P_{1}, P_{2}) except those close encounters.

For example, let (P_{1}, P_{2}) be the first pair of paths in Figure 2. Then

E(P_{1}, P_{2}) = {(P_{1}, P_{2}), (Q_{1}, Q_{2})}, O(P_{1}, P_{2}) = {(P′_{1}, P′_{2}), (Q′_{1}, Q′_{2})}.

So

w(O(P_{1}, P_{2})) − w(E(P_{1}, P_{2})) = [w(P′_{1}, P′_{2}) + w(Q′_{1}, Q′_{2})] − [w(P_{1}, P_{2}) + w(Q_{1}, Q_{2})]
= (R_{0}R_{1} + S_{0}S_{1} − S_{0}R_{1} − R_{0}S_{1})r_{0}^{2}r_{1}t_{0}^{2}t_{1}
= (S_{0} − R_{0})(S_{1} − R_{1})r_{0}^{2}r_{1}t_{0}^{2}t_{1}.

[figure: (P_{1}, P_{2}); (Q_{1}, Q_{2}); (P′_{1}, P′_{2}); (Q′_{1}, Q′_{2})]

Figure 2.

It follows that w(E(P_{1}, P_{2})) ≤ w(O(P_{1}, P_{2})) since R_{k} ≤ S_{k} for all k ≥ 0 by the assumption in Theorem 1. Clearly, Callan’s operation induces an equivalence relation on 𝒞 and O(P_{1}, P_{2}) is an equivalence class. So we have

w(𝒞) = ∑ w(E(P_{1}, P_{2})) ≤ ∑ w(O(P_{1}, P_{2})) ≤ w(𝒞^{∗}),

where the summation runs over such equivalence classes of (P_{1}, P_{2}). This completes the proof of the inequality (6), as required.

3 Concluding remarks and further work

Our proof adapts to all Catalan-like numbers satisfying the assumption in Theorem 1, and in particular, to the Catalan numbers and the Bell numbers. A more interesting problem is to construct an injection σ : (M_{n}, M_{n}) → (M_{n+1}, M_{n−1}) such that w(P_{1}, P_{2}) ≤ w(σ(P_{1}, P_{2})). The Catalan-like numbers have various combinatorial interpretations [1, 2, 12, 13], so it is natural to find out other combinatorial proof of Theorem 1. We refer the reader to [6, 8, 10, 11] for some related techniques and topics.

It is well known that the sequence (a_{n})_{n≥0} is log-convex if and only if a_{m}a_{n} ≤ a_{n+1}a_{m−1} for n ≥ m ≥ 1. So the inequality (4) is equivalent to the inequality

w(M_{m}, M_{n}) ≤ w(M_{n+1}, M_{m−1}).  (7)

Place each pair of Motzkin paths in (M_{m}, M_{n}) or (M_{n+1}, M_{m−1}) such that the first begins from (0, 0) and the second ends at (n + 1, 0). Then the inequality (7) can be showed by the same technique used in the proof of the inequality (4).

Zhu [14] also gave the q-version of Theorem 1. For two polynomials f(q) and g(q), denote f(q) ≤_{q} g(q) if the difference g(q) − f(q) has only nonnegative coefficients. Let (f_{n}(q))_{n≥0} be a polynomial sequence. It is called q-log-convex if f_{n}^{2}(q) ≤_{q} f_{n+1}(q)f_{n−1}(q) for all n ≥ 1. It is called strongly q-log-convex if f_{m}(q)f_{n}(q) ≤_{q} f_{n+1}(q)f_{m−1}(q) for any n ≥ m ≥ 1. It is well known that the strong q-log-convexity implies the q-log-convexity but the converse is not true (see [5] for instance). The method of proof used in the log-convexity can be carried over verbatim to the q-log-convexity.

Theorem 2. ([14, Theorem 2.1]) Let (r_{n}(q))_{n≥0}, (s_{n}(q))_{n≥0} and (t_{n}(q))_{n≥1} be three sequences of polynomials with nonnegative coefficients. Assume that the triangular array (c_{n,k}(q))_{0≤k≤n} satisfies the recurrence

c_{n+1,k}(q) = r_{k−1}(q)c_{n,k−1}(q) + s_{k}(q)c_{n,k}(q) + t_{k+1}(q)c_{n,k+1}(q) for n, k ≥ 0,
c_{0,0}(q) = 1, c_{0,k}(q) = 0 for k ≠ 0.

If r_{k}(q)t_{k+1}(q) ≤_{q} s_{k}(q)s_{k+1}(q) for all k ≥ 0, then the sequence (c_{n,0}(q))_{n≥0} is strongly q-log-convex.

Liu and Wang [9] conjectured the q-log-convexity of sequences of Narayana polynomials of two types and Chen et al. [4, 5] proved them by means of the theory of symmetric functions. It immediately follows from Theorem 2 that such two sequences are actually strongly q-log-convex respectively. See Zhu [14] for details.

4 Acknowledgment

The authors thank the anonymous referee for his/her careful reading and helpful comments. This work was supported in part by the National Natural Science Foundation of China (Nos. 11071030, 11371078) and the Specialized Research Fund for the Doctoral Program of Higher Education of China (No. 20110041110039).

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, Spinger, Berlin, 2001, pp. 347– 390.

[3] D. Callan, Notes on Motzkin and Schröder numbers,

    http://www.stst.wisc.edu/~callan/papersother/.

[4] W. Y. C. Chen, R. L. Tang, L. X. W. Wang, and A. L. B. Yang, The q-log-convexity of the Narayana polynomials of type B, Adv. in Appl. Math. 44 (2010), 85–110.

[5] W. Y. C. Chen, L. X. W. Wang, and A. L. B. Yang, Schur positivity and the q-log-convexity of the Narayana polynomials, J. Algebraic Combin. 32 (2010), 303–338.

[6] T. Došlić, Seven (lattice) paths to log-convexity, Acta Appl. Math. 110 (2010), 1373– 1392.

[7] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.

[8] I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. Math. 58 (1985), 300–321.

[9] L. L. Liu and Y. Wang, On the log-convexity of combinatorial sequences, Adv. in Appl. Math. 39 (2007), 453–476.

[10] B. E. Sagan, Inductive and injective proofs of log concavity results, Discrete Math. 68 (1988), 281–292.

[11] B. E. Sagan, Log concave sequences of symmetric functions and analogs of the Jacobi-Trudi determinants, Trans. Amer. Math. Soc. 329 (1992), 795–811.

[12] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics 62, Cambridge University Press, 1999.

[13] R. P. Stanley, Catalan addendum,

    http://www-math.mit.edu/~rstan/ec/catadd.pdf.

[14] B. X. Zhu, Log-convexity and strong q-log-convexity for some triangular arrays, Adv. in Appl. Math. 50 (2013), 595–606.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 05A20. Keywords: Catalan-like number, log-convexity, weighted Motzkin path.

(Concerned with sequences \underline{A000108}, \underline{A000110}, \underline{A000957}, \underline{A000984}, \underline{A001006}, \underline{A002212}, \underline{A005043}, and \underline{A006318}.)

Received January 28 2014; revised version received March 17 2014. Published in Journal of Integer Sequences, March 23 2014.

Return to Journal of Integer Sequences home page.