Abstract
This paper does three things: It proves a central limit theorem for novel permutation statistics (for example, the number of descents plus the number of descents in the inverse). It provides a clear illustration of a new approach to proving central limit theorems more generally. It gives us an opportunity to acknowledge the work of our teacher and friend B. V. Rao.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. A. Bender, Central and local limit theorems applied to asymptotic enumeration, J. Combinatorial Theory Ser. A, 15 (1973), 91–111.
A. Borodin, P. Diaconis and J. Fulman, On adding a list of numbers (and other one-dependent determinantal processes), Bull. Amer. Math. Soc. (N.S.), 47(4) (2010), 639–670.
S. Chatterjee, A new method of normal approximation. Ann. Probab., 36(4) (2008), 1584–1610.
S. Chatterjee and K. Soundararajan, Random multiplicative functions in short intervals, Int. Math. Res. Not., 2012(3) (2012), 479–492.
L. Carlitz, Eulerian numbers and polynomials, Math. Mag., 32 (1958), 247–260.
L Carlitz, D. P. Roselle and R. A. Scoville, Permutations and sequences with repetitions by number of increases, J. Combinatorial Theory, 1 (1966), 350–374.
L. H. Y. Chen and Q.-M. Shao, Normal approximation under local dependence, Ann. Probab., 32(3A) (2004), 1985–2028.
M. A. Conger, A refinement of the Eulerian numbers, and the joint distribution of π(1) and Des(π) in Sn. Ars Combin., 95 (2010), 445–472.
D. E. Critchlow, Metric methods for analyzing partially ranked data, Springer Science & Business Media, (2012).
F. N. David and D. E. Barton, Combinatorial chance, Hafner Publishing Co., New York, (1962).
P. Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics, Hayward, CA, (1988).
J. Fulman, Descent identities, Hessenberg varieties, and the Weil conjectures, J. Combin. Theory Ser. A, 87(2) (1999), 390–397.
J. Fulman, Stein’s method and non-reversible Markov chains, In Stein’s method: expository lectures and applications, 69–77, IMS Lecture Notes Monogr. Ser., 46, Inst. Math. Statist., Beachwood, OH (2004).
A. M. Garsia and I. Gessel, Permutation statistics and partitions. Adv. in Math., 31(3) (1979), 288–305.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete mathematics. A foundation for computer science, Second edition, Addison-Wesley Publishing Company, Reading, MA, (1994).
L. H. Harper, Stirling behavior is asymptotically normal, Ann. Math. Statist., 38 (1967), 410–414.
J. I. Marden, Analyzing and modeling rank data, CRC Press, (1996).
T. K. Petersen, Two-sided Eulerian numbers via balls in boxes. Math. Mag., 86(3) (2013), 159–176.
T. K. Petersen, Eulerian numbers, Birkhäuser/Springer, New York, (2015).
J. Pitman, Probabilistic bounds on the coefficients of polynomials with only real zeros, J. Combin. Theory Ser. A, 77(2) (1997), 279–303.
D. Rawlings, Enumeration of permutations by descents, idescents, imajor index, and basic components. J. Combin. Theory Ser. A, 36(1) (1984), 1–14.
N. J. A. Sloane, A handbook of integer sequences, Academic Press, New York-London, (1973).
R. Stanley, Eulerian partitions of a unit hypercube, In: Higher Combinatorics (M. Aigner, ed.), Reidel, Dordrecht/Boston, 49 (1977).
R. P. Stanley, Enumerative combinatorics, Volume 1, Second edition, Cambridge University Press, Cambridge, (2012).
S. M. Stigler, Estimating serial correlation by visual inspection of diagnostic plots, Amer. Statist., 40(2) (1986), 111–116.
V. A. Vatutin, Limit theorems for the number of ascending segments in random permutations generated by sorting algorithms. Discrete Math. Appl., 4(1) (1994), 31–44.
V. A. Vatutin, The numbers of ascending segments in a random permutation and in one inverse to it are asymptotically independent, Discrete Math. Appl., 6(1) (1996), 41–52.
V. A. Vatutin and V. G. Mikhailov, On the number of readings of random nonequiprobable files under stable sorting, Discrete Math. Appl., 6(3) (1996), 207–223.
D. Warren and E. Seneta, Peaks and Eulerian numbers in a random sequence. J. Appl. Probab., 33(1) (1996), 101–114.
Author information
Authors and Affiliations
Corresponding author
Additional information
Sourav Chatterjee’s research was partially supported by NSF grant DMS-1441513.
Persi Diaconis’s research was partially supported by NSF grant DMS-1208775.
Rights and permissions
About this article
Cite this article
Chatterjee, S., Diaconis, P. A central limit theorem for a new statistic on permutations. Indian J Pure Appl Math 48, 561–573 (2017). https://doi.org/10.1007/s13226-017-0246-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13226-017-0246-3