<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Counting Simsun Permutations by Descents
Chak-On Chow1 and Wai Chee Shiu2
1Department of Mathematics and Information Technology, Hong Kong Institute of Education, 10 Lo Ping Road, Tai Po, New Territories, Hong Kong
2Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong
Annals of Combinatorics 15 (4) pp.625-635 December, 2011
AMS Subject Classification: 05A15; 05A19, 05A05, 05E05, 05E10
We count in the present work simsun permutations of length n by their number of descents. Properties studied include the recurrence relation and real-rootedness of the generating function of the number of n-simsun permutations with k descents. By means of generating function arguments, we show that the descent number is equidistributed over n-simsun permutations and n-André permutations. We also compute the mean and variance of the random variable Xn taking values the descent number of random n-simsun permutations, and deduce that the distribution of descents over random simsun permutations of length n satisfies a central and a local limit theorem as n→+∞.
Keywords: simsun permutations, descents, Andr´e trees, asymptotically normal


1. André, D.: Développements de sec x et de tang x. C.R. Acad. Sci. Paris 88, 965–967 (1879)

2. Bender, E.A.: Central and local limit theorems applied to asymptotic enumeration. J. Combin. Theory Ser. A 15, 91–111 (1973)

3. Brenti, F.: Unimodal, log-concave and Pólya frequency sequences in combinatorics. Mem. Amer. Math. Soc. 81, no. 413 (1989)

4. Canfield, E.R.: Central and local limit theorems for the coefficients of polynomials of binomial type. J. Combin. Theory Ser. A 23(3), 275–290 (1977)

5. Foata, D., Han, G.-N.: Arbres minimax et polynômes d’André. Adv. Appl. Math. 27(2-3), 367–389 (2001)

6. Foata, D., Schützenberger, M.-P.: Nombres d’Euler et permutations alternantes. In: Bose, R.C. (Ed.) A Survey of Combinatorial Theory, pp. 173–187, North-Holland, Amsterdam (1973)

7. Courant, R., Hilbert, D.: Methods of Mathematical Physics, Vol. 2. John Wiley & Sons, Inc., New York (1989)

8. Hetyei, G.: On the cd-variation polynomials of André and simsun permutations. Discrete Comput. Geom. 16(3), 259–275 (1996)

9. Hetyei, G., Reiner, E.: Permutation trees and variation statistics. European J. Combin. 19(7), 847–866 (1998)

10. Pitman, J.: Probabilistic bounds on the coefficients of polynomials with only real zeros. J. Combin. Theory Ser. A 77(2), 279–303 (1997)

11. Purtill, M.: André permutations, lexicographic shellability, and the cd-index of a convex polytope. Trans. Amer. Math. Soc. 338(1), 77–104 (1993)

12. Sachkov, V.N.: Combinatorial Methods in Discrete Mathematics. Cambridge University Press, Cambridge (1996)

13. Stanley, R.P.: Flag f -vectors and the cd-index. Math. Z. 216(3), 483–499 (1994)

14. Stanley, R.P.: Enumerative Combinatorics, Vol. 1. Cambridge University Press, Cambridge (1997)

15. Sundaram, S.: The homology of partitions with an even number of blocks. J. Algebraic Combin. 4(1), 69–92 (1995)

16. Sundaram, S.: Plethysm, partitions with an even number of blocks and Euler Numbers. In: Billera, L.J. et al (eds.) DIMACS Ser. Discrete Math. Theoret. Comput. Sci. Vol. 24, pp. 171–198. Amer. Math. Soc., Providence, RI (1996)

17. Bernoulli Number — Wikipedia, the free encyclopedia.

18. Zeilberger, D.: Rodica Simion (1955–2000): An (almost) perfect enumerator and human being. Available at http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/simion.html