Involutions avoiding the class of permutations in Sk with prefix 12

W. M. B. Dukes, Toufik Mansour

Research output: Contribution to conferencePaper

Abstract

An involution π is said to be τ-avoiding if it does not contain any subsequence having all the same pairwise comparisons as τ. This paper concerns the enumeration of involutions which avoid a set Ak of subsequences increasing both in number and in length at the same time. Let Ak be the set of all the permutations 12π3 . . . πk of length k. For k = 3 the only subsequence in Ak is 123 and the 123-avoiding involutions of length n are enumerated by the central binomial coefficients. For k = 4 we give a combinatorial explanation that shows the number of involutions of length n avoiding A4 is the same as the number of symmetric Schroder paths of length n − 1. For each k ≥ 3 we determine the generating function for the number of involutions avoiding the subsequences in Ak, according to length, first entry and number of fixed points.
Original languageEnglish
Publication statusPublished - 2007
Event19th International Conference on Formal Power Series & Algebraic Combinatorics - Nankai University, Tianjin, China
Duration: 2 Jul 20076 Jul 2007

Conference

Conference19th International Conference on Formal Power Series & Algebraic Combinatorics
Abbreviated titleFPSAC'07
CountryChina
CityTianjin
Period2/07/076/07/07

Keywords

  • involutions
  • forbidden subsequences
  • Schroder paths
  • symmetric Schroder paths

Cite this

Dukes, W. M. B., & Mansour, T. (2007). Involutions avoiding the class of permutations in Sk with prefix 12. Paper presented at 19th International Conference on Formal Power Series & Algebraic Combinatorics, Tianjin, China.