×

Enumerations of permutations by circular descent sets. (English) Zbl 1445.05009

Summary: The circular descent of a permutation \(\sigma\) is a set \(\{ \sigma(i) \mid \sigma(i) > \sigma(i+1) \}\). In this paper, we focus on the enumerations of permutations by the circular descent set. Let \(\operatorname{cdes}_n(S)\) be the number of permutations of length \(n\) which have the circular descent set \(S\). We derive the explicit formula for \(\operatorname{cdes}_n(S)\). We describe a class of generating binary trees \(T_k\) with weights. We find that the number of permutations in the set \(\operatorname{CDES}_n(S)\) corresponds to the weights of \(T_k\). As a application of the main results in this paper, we also give the enumeration of permutation tableaux according to their shape.

MSC:

05A15 Exact enumeration problems, generating functions
05A05 Permutations, words, matrices
05E10 Combinatorial aspects of representation theory
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] F. R. K. Chung, R. L. Graham, V. E. Hoggat, Jr. and M. Kleiman, The number of Baxter permutations, J. Combin. Theory Ser. A 24 (1978), no. 3, 382-394. · Zbl 0398.05003
[2] S. Corteel, Crossings and alignments of permutations, Adv. in Appl. Math. 38 (2007), no. 2, 149-163. · Zbl 1121.05003
[3] S. Corteel and P. Nadeau, Bijections for permutaion tableaux, European J. Combin. 30 (2009), no. 1, 295-310. · Zbl 1167.05003
[4] S. Corteel and L. K. Williams, Permutation tableaux and the asymmetric exclusion process, Adv. in Appl. Math. 39 (2006), no. 3, 293-310. · Zbl 1205.05243
[5] —-, A Markov chain on permutations which projects to the PASEP, Int. Math. Res. Not. IMRN 2007 (2007), no. 17, Art. ID rnm055, 27 pp. · Zbl 1132.60070
[6] M. Domaratzki, Combinatorial Interpretations of a generalization of the Genocchi numbers, J. Integer Seq. 7 (2004), no. 3, Article 04.3.6, 11 pp. · Zbl 1092.11010
[7] D. Dumont, Sur une conjecture de Gandhi concernant les nombres de Genocchi, Discrete Math. 1 (1972), no. 4, 321-327. · Zbl 0263.10005
[8] —-, Interprétations combinatoires des nombres de Genocchi, Duke Math. J. 41 (1974), 305-318.
[9] D. Dumont and D. Foata, Une propriété de symétrie des nombres de Genocchi, Bull. Soc. Math. France 104 (1976), no. 4, 433-451. · Zbl 0362.05018
[10] D. Dumont and A. Randrianarivony, Dérangements et nombres de Genocchi, Discrete Math. 132 (1994), no. 1-3, 37-49. · Zbl 0807.05001
[11] D. Dumont and G. Viennot, A combinatorial interpretation of the Seidel generation of Genocchi numbers, Ann. Discrete. Math. 6 (1980), 77-87. · Zbl 0449.10011
[12] J. M. Gandhi, A conjectured representation of Genocchi numbers, Amer. Math. Monthly 77 (1970), no. 5, 505-506. · Zbl 0198.37003
[13] A. Postnikov, Total positivity, Grassmannians, and networks..
[14] J. Riordan and P. R. Stein, Proof of a conjecture on Genocchi numbers, Discrete Math. 5 (1973), 381-388. · Zbl 0271.05004
[15] E. Steingrimsson and L. K. Willams, Permutation tableaux and permutation patterns, J. Combin. Theory Ser. A 114 (2007), no. 2, 211-234. · Zbl 1116.05003
[16] L. K. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005), no. 2, 319-342. · Zbl 1064.05150
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.