<%@ 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
cchow@alum.mit.edu
2Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong
wcshiu@hkbu.edu.hk
Annals of Combinatorics 15 (4) pp.625-635 December, 2011
AMS Subject Classification: 05A15; 05A19, 05A05, 05E05, 05E10
Abstract:
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

References:

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