On the log-convexity of combinatorial sequences. (English) Zbl 1131.05010
The paper studies log-convexity of combinatorial sequences. It is shown that log-convexity is preserved under componentwise sum, under binomial convolution, and by linear transformations given by matrices of binomial coefficients and Stirling numbers of both kinds. Techniques are developed to prove the log-convexity of sequences satisfying a three-term recurrence. These techniques show the log-convexity of the central binomial coefficients, the Catalan numbers, the Motzkin numbers, the Fine numbers, the central Delannoy numbers, the little and large Schröder numbers, and derangements. If \(F_n\), \(L_n\) and \(P_n\) denote Fibonacci, Lucas and Pell numbers respectively, then the bisections \(\{F_{2n+1}\}\), \(\{L_{2n}\}\), and \(\{P_{2n+1}\}\) are log-concave, while the bisections \(\{F_{2n}\}\), \(\{L_{2n+1}\}\), and \(\{P_{2n}\}\) are log-convex.
Stanley suggested the following definition for \(q\)-log-convexity. For two real polynomials \(f(q)\) and \(g(q)\), write \(f(q) \leq_q g(q)\) if \(f(q) - g(q)\) has non-negative coefficients as a polynomial. A sequence of real polynomials \(P_n(q)\) is called \(q\)-log-convex, if \(P_n^2(q) \leq_q P_{n-1}(q)P_{n+1}(q)\). Bell and Eulerian polynomials, \(q\)-Schröder and \(q\)-Delannoy numbers are shown to be log-convex.
The \(q\)-log-convexity of Narayana polynomials is posed as a conjecture, together with conjectures about certain transformations keeping \(q\)-log-convexity.
Stanley suggested the following definition for \(q\)-log-convexity. For two real polynomials \(f(q)\) and \(g(q)\), write \(f(q) \leq_q g(q)\) if \(f(q) - g(q)\) has non-negative coefficients as a polynomial. A sequence of real polynomials \(P_n(q)\) is called \(q\)-log-convex, if \(P_n^2(q) \leq_q P_{n-1}(q)P_{n+1}(q)\). Bell and Eulerian polynomials, \(q\)-Schröder and \(q\)-Delannoy numbers are shown to be log-convex.
The \(q\)-log-convexity of Narayana polynomials is posed as a conjecture, together with conjectures about certain transformations keeping \(q\)-log-convexity.
Reviewer: László A. Székely (Columbia)
MSC:
| 05A20 | Combinatorial inequalities |
| 11B73 | Bell and Stirling numbers |
| 11B83 | Special sequences and polynomials |
| 11B37 | Recurrences |
Software:
OEISReferences:
| [1] | Aigner, M., Motzkin numbers, European J. Combin., 19, 663-675 (1998) · Zbl 0915.05004 |
| [2] | Bender, E. A.; Canfield, E. R., Log-concavity and related properties of the cycle index polynomials, J. Combin. Theory Ser. A, 74, 57-70 (1996) · Zbl 0853.05013 |
| [3] | Bonin, J.; Shapiro, L.; Simion, R., Some \(q\)-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, J. Statist. Plann. Inference, 34, 35-55 (1993) · Zbl 0783.05008 |
| [4] | Brenti, F., Unimodal, log-concave, and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc., 413 (1989) · Zbl 0697.05011 |
| [5] | Brenti, F., Log-concave and unimodal sequences in algebra, combinatorics, and geometry: An update, (Contemp. Math., vol. 178 (1994)), 71-89 · Zbl 0813.05007 |
| [6] | Brenti, F., Combinatorics and total positivity, J. Combin. Theory Ser. A, 71, 175-218 (1995) · Zbl 0851.05095 |
| [7] | Brenti, F., The applications of total positivity to combinatorics, and conversely, (Total Positivity and Its Applications. Total Positivity and Its Applications, Jaca, 1994. Total Positivity and Its Applications. Total Positivity and Its Applications, Jaca, 1994, Math. Appl., vol. 359 (1996), Kluwer: Kluwer Dordrecht), 451-473 · Zbl 0895.05001 |
| [8] | Callan, D., Notes on Motzkin and Schröder numbers |
| [9] | Comtet, L., Advanced Combinatorics (1974), Reidel: Reidel Dordrecht · Zbl 0283.05001 |
| [10] | Davenport, H.; Pólya, G., On the product of two power series, Canad. J. Math., 1, 1-5 (1949) · Zbl 0037.32505 |
| [11] | Došlić, T., Log-balanced combinatorial sequences, Int. J. Math. Math. Sci., 4, 507-522 (2005) · Zbl 1073.05005 |
| [12] | Došlić, T., Logarithmic behavior of some combinatorial sequences · Zbl 1147.05012 |
| [13] | Došlić, T.; Svrtan, D.; Veljan, D., Enumerative aspects of secondary structures, Discrete Math., 285, 67-82 (2004) · Zbl 1044.05008 |
| [14] | Došlić, T.; Veljan, D., Calculus proofs of some combinatorial inequalities, Math. Inequal. Appl., 6, 197-209 (2003) · Zbl 1029.05009 |
| [15] | Ehrenfeucht, A.; Harju, T.; ten Pas, P.; Rozenberg, G., Permutations, parenthesis words, and Schröder numbers, Discrete Math., 190, 259-264 (1998) · Zbl 0956.05011 |
| [16] | Engel, K., On the average rank of an element in a filter of the partition lattice, J. Combin. Theory Ser. A, 65, 67-78 (1994) · Zbl 0795.05051 |
| [17] | Foata, D.; Zeilberger, D., A classic proof of a recurrence for a very classical sequence, J. Combin. Theory Ser. A, 80, 380-384 (1997) · Zbl 0883.05007 |
| [18] | Gessel, I.; Viennot, G., Binomial determinants, path, and hook length formulae, Adv. Math., 58, 300-321 (1985) · Zbl 0579.05004 |
| [19] | Guy, R. K., Catwalks, sandsteps and Pascal pyramids, J. Integer Seq., 3 (2000), Article 00.1.6 · Zbl 1064.05014 |
| [20] | Harary, F.; Read, R. C., The enumeration of tree-like polyhexes, Proc. Edinb. Math. Soc. (2), 17, 1-13 (1970) · Zbl 0201.26104 |
| [21] | Karlin, S., Total Positivity, vol. I (1968), Stanford Univ. Press: Stanford Univ. Press Stanford · Zbl 0219.47030 |
| [22] | Kurtz, D. C., A note on concavity properties of triangular arrays of numbers, J. Combin. Theory Ser. A, 13, 135-139 (1972) · Zbl 0263.05029 |
| [23] | Liu, L. L.; Wang, Y., A unified approach to polynomial sequences with only real zeros, Adv. in Appl. Math. (2006) |
| [24] | Peart, P.; Woan, W.-J., Bijective proofs of the Catalan and fine recurrences, Congr. Numer., 137, 161-168 (1999) · Zbl 0971.05004 |
| [25] | Peart, P.; Woan, W.-J., A bijective proof of the Delannoy recurrence, Congr. Numer., 158, 29-33 (2002) · Zbl 1030.05003 |
| [26] | Roman, S., The Umbral Calculus (1984), Academic Press: Academic Press New York · Zbl 0536.33001 |
| [27] | Sagan, B. E., Inductive and injective proofs of log concavity results, Discrete Math., 68, 281-292 (1988) · Zbl 0658.05003 |
| [28] | Sagan, B. E., Log concave sequences of symmetric functions and analogs of the Jacobi-Trudi determinants, Trans. Amer. Math. Soc., 329, 795-811 (1992) · Zbl 0769.05097 |
| [29] | Sagan, B. E., Inductive proofs of \(q\)-log concavity, Discrete Math., 99, 298-306 (1992) · Zbl 0764.05096 |
| [30] | Sagan, B. E., Unimodality and the reflection principle, Ars Combin., 48, 65-72 (1998) · Zbl 0962.05003 |
| [31] | Sloane, N. J.A., The On-Line Encyclopedia of Integer Sequences · Zbl 1274.11001 |
| [32] | Stanley, R. P., Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann. New York Acad. Sci., 576, 500-534 (1989) · Zbl 0792.05008 |
| [33] | Stanley, R. P., Enumerative Combinatorics, vol. 1 (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, UK · Zbl 0889.05001 |
| [34] | Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, UK · Zbl 0928.05001 |
| [35] | Sulanke, R. A., Bijective recurrences concerning Schröder paths, Electron. J. Combin., 5 (1998), Research Paper 47, 11 pp · Zbl 0913.05007 |
| [36] | Sulanke, R. A., Bijective recurrences for Motzkin paths, Adv. in Appl. Math., 27, 627-640 (2001) · Zbl 0992.05015 |
| [37] | Sulanke, R. A., The Narayana distribution, J. Statist. Plann. Inference, 101, 311-326 (2002) · Zbl 1001.05009 |
| [38] | Sulanke, R. A., Objects counted by the central Delannoy numbers, J. Integer Seq., 6 (2003), Article 03.1.5, 19 pp · Zbl 1012.05008 |
| [39] | Swamy, M. N.S., Further properties of Morgan-Voyce polynomials, Fibonacci Quart., 6, 167-175 (1968) · Zbl 0155.08204 |
| [40] | Theodorescu, R.; Borwein, J. M., Problems and Solutions: Solutions: Moments of the Poisson distribution: 10738, Amer. Math. Monthly, 107, 659 (2000) |
| [41] | Wang, Y., A simple proof of a conjecture of Simion, J. Combin. Theory Ser. A, 100, 399-402 (2002) · Zbl 1013.05011 |
| [42] | Wang, Y., Proof of a conjecture of Ehrenborg and Steingrímsson on excedance statistic, European J. Combin., 23, 355-365 (2002) · Zbl 1010.05001 |
| [43] | Wang, Y., Linear transformations preserving log-concavity, Linear Algebra Appl., 359, 161-167 (2003) · Zbl 1015.15002 |
| [44] | Wang, Y.; Yeh, Y.-N., Proof of a conjecture on unimodality, European J. Combin., 26, 617-627 (2005) · Zbl 1076.05010 |
| [45] | Wang, Y.; Yeh, Y.-N., Polynomials with real zeros and Pólya frequency sequences, J. Combin. Theory Ser. A, 109, 63-74 (2005) · Zbl 1057.05007 |
| [46] | Wang, Y.; Yeh, Y.-N., Log-concavity and LC-positivity, J. Combin. Theory Ser. A, 114, 195-210 (2007) · Zbl 1109.11019 |
| [47] | West, J., Generating trees and the Catalan and Schröder numbers, Discrete Math., 146, 247-262 (1995) · Zbl 0841.05002 |
| [48] | Wilf, H. S., A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects, Adv. Math., 24, 281-291 (1977) · Zbl 0354.05041 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
