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.
- pattern avoiding permutations
- graph of overlapping permutations