Finite transition matrices for permutations avoiding pairs of length four patterns

Darla Kremer*, Wai Chee SHIU

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)

Abstract

We show that the four classes of pattern avoiding permutations, S n(1234,3214), S n(4123,3214), S n(2341,2143) and S n(1234,2143) are enumerated by the formula (4 n-1+2)/3. In an electronic appendix we provide finite transition matrices for the number |S n(u,v)| of permutations avoiding pairs (u,v) of length four patterns where u contains the subsequence 123 and v contains the subsequence 321 as well as a transition matrix for |S n(1234,43215)|.

Original languageEnglish
Pages (from-to)171-183
Number of pages13
JournalDiscrete Mathematics
Volume268
Issue number1-3
DOIs
Publication statusPublished - 6 Jul 2003

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Forbidden subsequences
  • Pattern avoiding permutations
  • Restricted permutations

Fingerprint

Dive into the research topics of 'Finite transition matrices for permutations avoiding pairs of length four patterns'. Together they form a unique fingerprint.

Cite this