A note on log-convexity of q-Catalan numbers L.M. Butler and W.P. Flanigan∗ The sequence of Catalan numbers (1,1,2,5,14,...) is defined by C = 1 0 and the recursion n C = C C , n+1 k n−k 7 kX=0 0 0 from which it is evident that the sequence is nondecreasing. From the well- 2 known formula C = 1 2n it is also easily seen that C C ≥ C 2 for n n+1 n k−1 k+1 k n k ≥ 1. Equivalently, the s(cid:16)equ(cid:17)ence satisfies the log-convexity result that a J C C −C C is nonnegative for ℓ ≥ k ≥ 1. 2 k−1 ℓ+1 k ℓ ] Many polynomials in q have been called q-Catalan numbers. See [3]. O These polynomials have nonnegative coefficients and evaluate at q = 1 to C Catalan numbers. One such sequence, studied by Carlitz and Riordan in [2], . h (1,1,1+q,1+q+2q2+q3,1+q+2q2+3q3+3q4+3q5+q6,...) is defined t a by C (q) = 1 and the recursion m 0 [ n 1 Cn+1(q) = q(k+1)(n−k)Ck(q)Cn−k(q). v kX=0 5 The recursion shows that the sequence is nondecreasing: C (q)−C (q) has 6 n+1 n 0 nonnegative coefficients for n ≥ 0. No formula is known for C (q) and it is n 1 not true that C (q)C (q)−C (q)2 has nonnegative coefficients. But it is true 0 2 4 3 7 that C (q)C (q) − qC (q)2 has nonnegative coefficients for k ≥ 1. Our k−1 k+1 k 0 main result that / h at Ck−1(q)Cℓ+1(q)−qℓ−k+1Ck(q)Cℓ(q) has nonnegative coefficients for ℓ ≥ k ≥ 1 m : is more general than the special case for k = ℓ. v i Other authors [4] have defined a sequence of polynomials {P (q)} to X n n≥0 be q-log-convex if P (q)P (q) − P (q)2 has nonnegative coefficients for r k−1 k+1 k a k ≥ 1. We do not advocate this definition, since it does not imply that P (q)P (q) − P (q)P (q) has nonnegative coefficients for ℓ ≥ k ≥ 1. k−1 ℓ+1 k ℓ Consider 1+ q +q2 +q5,1+q2 +q3,1+ q +q3,1+ 2q +q6. Log-convexity for sequences of nonzero polynomials with nonnegative coefficients is more subtle than log-convexity for sequences of positive numbers. ∗Research initiated in Pat Flanigan’s senior thesis, under Lynne Butler’s direction at HaverfordCollege, Haverford PA 19041 USA. 1 To prove our log-convexity result, we use the combinatorial interpretation C (q) = qinvπ, k Xπ where the sum is over permutations with k 1s and k 2s such that every initial segment has no more 2s than 1s. For example, C (q) = 1 + q + 2q2 + q3, 3 since the permutations 111222, 112122, 121122, 112212 and 121212 have inversion numbers 0, 1, 2, 2 and 3, respectively. Such a permutation may be visualized as a path in a k × k square from the lower left corner to the upper right corner. If the permutation is read left to right, where 1 denotes a horizontal step and 2 denotes a vertical step, then the path never rises above the diagonal. The inversion number of the permutation is the area below the path. Such permutations, called lattice permutations, were studied by MacMahon [5]. Theorem: The q-Catalan numbers C (q) = qinvπ, where the sum is over k π lattice permutations with k 1s and k 2s, satisPfy: C (q)C (q)−qℓ−k+1C (q)C (q) has nonnegative coefficients for k ≤ ℓ. k−1 ℓ+1 k ℓ The proof of the above result uses an injection introduced by Butler [1] to prove a similar log-concavity result for q-binomial coefficients: n n n n −qℓ−k+1 has nonnegative coefficients for k ≤ ℓ. (cid:20)k(cid:21) (cid:20)ℓ(cid:21) (cid:20)k −1(cid:21) (cid:20)ℓ+1(cid:21) q q q q Proof of the Theorem: Given k ≤ ℓ, we define an injection ϕ : P ×P → P ×P k ℓ k−1 ℓ+1 where P is the set of lattice permutations with n 1s and n 2s. Then we show n that if ϕ(π,σ) = (ν,ω), we have invπ +invσ +(ℓ−k +1) = invν +invω. Let (π,σ) ∈ P ×P be given. For 0 ≤ i ≤ 2k −2, consider k ℓ ν(i) = σ ···σ π ···π 1 i i+3 2k ω(i) = π ···π π π σ ···σ 1 i i+1 i+2 i+1 2ℓ Define ϕ(π,σ) = (ν(i),ω(i)) = (σ π ,π σ ), where i is smallest such that L R L R the number of 2s in π exceeds the number of 2s in σ by exactly 1. (Note L L that π = π π and σ = ∅ if i = 0, but π = π and σ = σ ···σ if L 1 2 L L L 1 2k−2 i = 2k −2. Initially π has at most one more 2 than σ , and finally π has L L L at least one more 2 than σ .) L 2 To show that (ℓ−k + 1)+invπ +invσ = invσ π +invπ σ , we use L R L R the fact that the number of 2s in π , denoted m π , equals m σ +1; hence L 2 L 2 L the number of 1s in π , denoted m π , equals m σ +1. Since an inversion L 1 L 1 L 21 in a permutation may occur in the left portion, occur in the right portion, or straddle the left and right portions, we have: invπ = invπ +invπ +(m π )(m π ) L R 2 L 1 R invσ = invσ +invσ +(m σ )(m σ ) L R 2 L 1 R invπ σ = invπ +invσ +(m π )(m σ ) L R L R 2 L 1 R invσ π = invσ +invπ +(m σ )(m π ) L R L R 2 L 1 R invπ σ +invσ π −invπ −invσ = (m π −m σ )(m σ −m π ) L R L R 2 L 2 L 1 R 1 R = m σ −m π 1 R 1 R = (ℓ−m σ )−(k −m π ) 1 L 1 L = ℓ−k +1 Corollary: For 1 ≤ r ≤ k and ℓ > k −r, C (q)C (q)−qr(ℓ−k+r)C (q)C (q) has nonnegative coefficients. k−r ℓ+r k ℓ Note that no higher power of q may be used. To see this, note that C (q) is n monic of degree n . So degC (q)C (q) = degqr(ℓ−k+r)C (q)C (q). 2 k−r ℓ+r k ℓ (cid:16) (cid:17) This corollary may be proved by induction on r or may be proved using aninjection like theone aboveforr = 1. To visualize thisinjection ϕ, picture π as a lattice path L from the lower left corner to the upper right corner of π a k×k square and picture σ as a lattice path L from the lower left corner to σ the upper right corner of a ℓ×ℓ square. Arrangethese inside a (ℓ+r)×(ℓ+r) square with the lattice path L beginning in the lower left corner and the π lattice path L ending in the upper right corner. Find the point where L σ π first meets L . If ϕ(π,σ) = (ν,ω), then the lattice path L follows L until σ ω π this point then follows L , and the lattice path L follows L until this point σ ν σ then follows L . The exponent r(ℓ−k+r) is the area of the rectangle in the π lower right of the (ℓ+r)×(ℓ+r) square that lies to the right of the k ×k square in the lower left and lies below the ℓ×ℓ square in the upper right. 3 Example: Terms in q2(3)C (q)C (q) and C (q)C (q), are compared below: 6 7 4 9 112112221122 12121122 7→ 12111212212212 112112211212212212 r r b b 7→ r b b r The example shows how the injection from P ×P to P ×P maps 6 7 4 9 (π,σ) = (112112221122,12111212212212) to (σ π ,π σ ) = (12121122,112112211212212212). L R L R The permutation π is the red lattice path in the 6×6 square, and σ is the blue lattice path in the 7 × 7 square. The 6 × 6 and 7 × 7 square overlap inside the 9 × 9 square at left. At right, a 4× 4 square is inside the 9 × 9 square. In the 4×4 square is the lattice path σ π , and in the 9×9 square L R is the lattice path π σ . The term in q2(3)C (q)C (q) corresponding to (π,σ) L R 6 7 is q2(3)+10+15, because the area under π is 10 and the area under σ is 15. The term in C (q)C (q) corresponding to (σ π ,π σ ) is q5+26 because the area 4 9 L R L R under σ π is 5 and the area under π σ is 26. L R L R References: [1] L. M. Butler, “The q-log-concavity of q-binomial coefficients”, J. Combin. Theory Ser. A 54 (1990), 54–63. [2] L. Carlitz and J. Riordan, “Two element lattice permutations and their q-generalization”, Duke J. Math. 31 (1964), 371–388. [3] J. Fu¨rlinger and J. Hofbauer, “q-Catalan numbers”, J. Combin. Theory Ser. A 40 (1985), 248–264. [4] Li Liu and Yi Wang, “On the log-convexity of combinatorial sequences”, to appear in Advances in Applied Mathematics, arXiv:math.CO/0602672. [5] P. A. MacMahon, Combinatory Analysis, Vol. I, Cambridge, 1915. 4