Log-concavity and related properties of the cycle index polynomials
type: Item
instance of: scholarly article
title: Log-concavity and related properties of the cycle index polynomials
zbMATH Open document ID: 0853.05013
author: Edward A. Bender
author: E. Rodney Canfield
published in: Journal of Combinatorial Theory. Series A
publication date: 1996-07-09T00:00:00Z
review text: Let \(X_0 = 1\), \(X_1, X_2, \dots\) be a log-concave sequence of nonnegative real numbers (i.e., \(X^2_i \geq X_{i - 1} X_{i + 1}\) for all \(i \geq 1)\), and let \(A_n\) be the cycle index polynomial of the symmetric group of order \(n\), i.e., the \(A_n\)'s are defined by \[ \sum_{n \geq 0} A_n u^n = \exp \Bigl( \sum_{j \geq 1} X_j u^j/j \Bigr). \] Then the main theorem of this paper asserts that \(A_{n - 1} A_{n + 1} \leq A^2_n \leq {n + 1 \over n} A_{n - 1} A_{n + 1}\). This implies that the coefficients of the formal power series \(\exp (g(u))\) are log-concave whenever the coefficients of the formal power series \(g(u)\) satisfy a condition slighlty weaker than log-concavity. As corollaries, the authors are able to show log-concavity of several familiar sequences, for which it was not known previously. The proof of the first inequality is inductively and actually establishes that the difference \(A^2_n - A_{n - 1} A_{n + 1}\) can be written as a polynomial with nonnegative coefficients in the expressions \(X_j\) and \(X_j X_k - X_{j - 1} X_{k + 1}\), \(j \leq k\). The second inequality is proven combinatorially, by working with what the authors call ``marked permutations''. Finally, it is shown that the same inequalities will hold for \(n\) sufficiently large without assuming log-concavity for the \(X_j\)'s, as long as only a finite number of \(X_j\)'s is nonzero.
Mathematics Subject Classification ID: 05A20
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A10
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 05A18
zbMATH DE Number: 883801
zbMATH Keywords: marked permutations
zbMATH Keywords: log-concave sequence
zbMATH Keywords: cycle index polynomial of the symmetric group
zbMATH Keywords: formal power series
zbMATH Keywords: log-concavity
zbMATH Keywords: inequality
reviewed by: C. Krattenthaler
MaRDI profile type: Publication
OpenAlex ID: W2098005496
DOI: 10.1006/JCTA.1996.0037
description: scientific article; zbMATH DE number 883801