Combinatorial Proofs of Log-concavity and Restricted Cycle Structure   
 

Miklós Bóna

Department of Mathematics, University of Florida, U.S.A.

bona@math.ufl.edu  
 

Abstract.      Full Text PDF

Let  be the number of permutations of length  having  cycles. It is well-known that the polynomial  has real roots only, and therefore, has log-concave coefficients. We will review some interesting generalizations of the problem, ask many open questions, and answer a few. Some of these questions are as follows.
 

1.Let  be the number of permutations of length  having  cycles, all of which have size at most . Does the polynomial  has real zeros only? Does it have log-concave coefficients?
 

2.Let  be the number of permutations of length  having  cycles, all of which have size larger than  (Such permutations are called -derangements). It has been proved by Brenti that the polynomial  has real roots only, consequently, it has Log-concave coefficients. Is there a combinatorial proof?
 

3.Let  be the number of permutations of length  in which all cycle lengths are at most . it has been proved by Canfield that then for any fixed , the sequence  is log-convex. Is there a combinatorial proof?
 

4.Let  be the number of -derangements. Is it true that the sequence  is log-convex for any fixed ? This is true for . Is there a combinatorial proof?