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 t he 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 ex p(g(u)) are log-concave whenever those of g(u) satisfy a condition sli ghtly weaker than log-concavity. The latter includes many familiar com binatorial sequences, only some of which were previously known to be l og-concave. To prove the first inequality we show that in fact the dif ference A(n)(2)-A(n-1)A(n+1) can be written as a polynomial with posit ive coefficients in the expression X(j) and X(j)X(k)-X(j-1)X(k+1), j l ess than or equal to k. The second inequality is proven combinatoriall y, by working with the notion of a marked permutation, which we introd uce 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 we ight, wt(M(i,j)) = x(j), and we relate the second inequality to proper ties of the weight enumerator polynomials. Finally, using asymptotic a nalysis, we show that the same inequalities hold for n sufficiently la rge 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.