Annals of Combinatorics 2 (1998) 111-129
Maximizing the Descent Statistic
Richard Ehrenborg1 and Swapneel Mahajan2
Department of Mathematics, White Hall, Cornell University, Ithaca, NY 14853-7901, USA
Received May 29, 1998
AMS Subject Classification: 05A05, 05A20
Abstract.For a subset S, let the descent statistic β (S) be the number of permutations that have descent set S.We study inequalities between the descent statistics of subsets. Each subset (and its complement) is encoded by a list containing the lengths of the runs. We define two preorders that compare different lists based on the descent statistic. Using these preorders, we obtain a complete order on lists of the form (ki,P,kn-i),where P is a palindrome, whose first entry is larger than k. We prove a conjecture due to Gessel, which determines the list that maximizes the descent statistic, among lists of a given size and given length. We also have a generalization of the boustrophedon transform of Millar, Sloane and Young.
Keywords: permutations, descent set, Euler numbers, Boustrophedon transform
1. M.D. Atkinson, How to compute the series expansions of sec(x) and tan(x), Amer. Math. Monthly 93 (1986) 387–389.
2. L.J. Billera, R. Ehrenborg, and M. Readdy, The ctd-index of oriented matroids, JCTA 80 (1997) 79–105.
3. A. Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980) 159–183.
4. N.G. de Bruijn, Permutations with given ups and downs, ,Nieuw Arch. Wisk 18 (1970) 61–65.
5. L. Carlitz, Permutations with prescribed pattern, Math. Nachr. 58 (1973) 31–53.
6. R. Ehrenborg and M. Readdy, The r-cubical lattice and a generalization of the cd-index, European J. Combin. 17 (1996) 709–725.
7. R. Ehrenborg and M. Readdy, Sheffer posets and r-signed permutations, Ann. Sci. Math. Quèbec 19 (1995) 173–196.
8. R. Ehrenborg and M. Readdy, Coproducts and the cd-index, J. Algebraic Combin..
9. H.O. Foulkes, Enumeration of permutations with prescribed up-down and inversion sequences, Discrete Math. 15 (1976) 235–252.
10. P.A. MacMahon, Combinatory Analysis, Vol. I, Chelsea Publishing Company, 1960, New York.
11. J. Millar, N.J.A. Sloane and N.E. Young, A new operation on sequences: The boustrophedon transform, JCTA 76 (1996) 44–54.
12. I. Niven, A combinatorial problem on finite sequences, Nieuw Arch. Wisk. 16 (1968) 116–123.
13. M. Purtill, Andrè permutations, lexicographic shellability and the cd-index of a convex polytope, Trans. Amer. Math. Soc. 338 (1993) 77–104.
14. M. Readdy, Extremal problems for the Möbius function, Michigan State University, 1993.
15. M. Readdy, Extremal problems in the face lattice of the n-dimensional octahedron, Discrete Math. 139 (1995) 361–380.
16. B.E. Sagan, Y.-N. Yeh and G. Ziegler, Maximizing Möbius functions on subsets of Boolean algebras, Discrete Math. 126 (1994) 293–311.
17. R.P. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth and Brooks/Cole, Monterey, CA, 1986.
18. E. Steingrìmsson, Permutation statistics of indexed permutations, European J. Combin. 15 (1994) 187–205.
19. G. Viennot, Permutations ayant une forme donnèe, Discrete Math. 26 (1979) 279–284.
20. G. Viennot, Èquidistribution des permutations ayant une forme donnèe selon les avances et coavances, JCTA 31 (1981) 43–55.