Log-Concavity and Related Properties of the Cycle Index Polynomials

LetAndenote thenth-cycle index polynomial, in the variablesXj, for the symmetric group onnletters. We show that if the variablesXjare assigned nonnegative real values which are log-concave, then the resulting quantitiesAnsatisfy the two inequalitiesAn−1An+1⩽A2n⩽((n+1)/n)An−1An+1. This implies that the coefficients of the formal power series exp(g(u)) are log-concave whenever those ofg(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 differenceA2n−An−1An+1can be written as a polynomial with positive coefficients in the expressionsXjandXjXk−Xj−1Xk+1,j⩽k. The second inequality is proven combinatorially, by working with the notion of amarkedpermutation, which we introduce in this paper. The latter is a permutation each of whose cycles is assigned a subset of available markers {Mi, j}. Each marker has aweight, wt(Mi, j)=xj, and we relate the second inequality to properties of theweight enumerator polynomials. Finally, using asymptotic analysis, we show that the same inequalities hold fornsufficiently large when theXjare fixed with only finite many nonzero values, with no additional assumption on theXj.