Number of cycles in the graph of 312-avoiding permutations

Ehrenborg, Richard and Kitaev, Sergey and Steingrimsson, Einar (2015) Number of cycles in the graph of 312-avoiding permutations. Journal of Combinatorial Theory Series A, 129. pp. 1-18. ISSN 0097-3165 (

[thumbnail of Ehrenborg-etal-JCTSA2015-number-of-cycles-in-the-graph-of-312-avoiding-permutations]
Text. Filename: Ehrenborg_etal_JCTSA2015_number_of_cycles_in_the_graph_of_312_avoiding_permutations.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (377kB)| Preview


The graph of overlapping permutations is defined in a way analogous to the De Bruijn graph on strings of symbols. That is, for every permutation π=π1π2...πn+1 there is a directed edge from the standardization of π1π2...πn to the standardization of π2π3...πn+1. We give a formula for the number of cycles of length d in the subgraph of overlapping 312-avoiding permutations. Using this we also give a refinement of the enumeration of 312-avoiding affine permutations and point out some open problems on this graph, which so far has been little studied.


Ehrenborg, Richard, Kitaev, Sergey ORCID logoORCID: and Steingrimsson, Einar ORCID logoORCID:;