Number of cycles in the graph of 312-avoiding permutations

Abstract

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 $\pi ={\pi }_1{\pi }_2...{\pi }_{n+1}$ there is a directed edge from the standardization of ${\pi }_1{\pi }_2...{\pi }_n$ to the standardization of ${\pi }_2{\pi }_3...{\pi }_{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.

To appear in the Journal of Combinatorial Theory - Series A

References in corpus (2)

• Arithmetic and growth of periodic orbits
• On uniquely k-determined permutations