Log-concavity and related properties of the cycle index polynomials

Let A(n) denote the nth-cycle index polynomial, in the variables X(j), for the symmetric group on n letters. We show that if the variables X(j) are assigned nonnegative real values which are log-concave, then the resulting quantities A(n) satisfy the two inequalities A(n-1)A(n+1) less than or equal to A(n)(2) less than or equal to ((n+1)/n)A(n-1)A(n+1). This implies that the coefficients of the formal power series exp(g(u)) are log-concave whenever those of g(u) satisfy a condition slightly weaker than log-concavity. The latter includes many familiar combinatorial sequences, only some of which were previously known to be log-concave. To prove the first inequality we show that in fact the difference A(n)(2)-A(n-1)A(n+1) can be written as a polynomial with positive coefficients in the expression X(j) and X(j)X(k)-X(j-1)X(k+1), j less than or equal to k. The second inequality is proven combinatorially, by working with the notion of a marked permutation, which we introduce in this paper. The latter is a permutation each of whose cycles is assigned a subset of available markers {M(i,j)}. Each marker has a weight, wt(M(i,j)) = x(j), and we relate the second inequality to properties of the weight enumerator polynomials. Finally, using asymptotic analysis, we show that the same inequalities hold for n sufficiently large when the X(j) are fixed with only finite many nonzero values, with no additional assumption on the X(j). (C) 1996 Academic Press, Inc.