Number of cycles in the graph of 312-avoiding permutations

Richard Ehrenborg, Sergey Kitaev, Einar Steingrímsson

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 π=π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.

Original languageEnglish
Pages (from-to)1-18
Number of pages18
JournalJournal of Combinatorial Theory. Series A
Volume129
DOIs
StatePublished - Jan 2015

Bibliographical note

Publisher Copyright:
© 2014 Elsevier Inc.

Keywords

  • Cycles
  • Graph of overlapping permutations
  • Pattern avoiding permutations

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Number of cycles in the graph of 312-avoiding permutations'. Together they form a unique fingerprint.

Cite this