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.

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.
Dukes, W. M. B. ; Mansour, Toufik. / 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.
@conference{71c4b606c9b84b7ba2fbcc05f874406d,
title = "Involutions avoiding the class of permutations in Sk with prefix 12",
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.",
keywords = "involutions, forbidden subsequences, Schroder paths, symmetric Schroder paths",
author = "Dukes, {W. M. B.} and Toufik Mansour",
year = "2007",
language = "English",
note = "19th International Conference on Formal Power Series & Algebraic Combinatorics, FPSAC'07 ; Conference date: 02-07-2007 Through 06-07-2007",

}

Dukes, WMB & 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, 2/07/07 - 6/07/07, .

Involutions avoiding the class of permutations in Sk with prefix 12. / Dukes, W. M. B.; Mansour, Toufik.

2007. Paper presented at 19th International Conference on Formal Power Series & Algebraic Combinatorics, Tianjin, China.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Involutions avoiding the class of permutations in Sk with prefix 12

AU - Dukes, W. M. B.

AU - Mansour, Toufik

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - involutions

KW - forbidden subsequences

KW - Schroder paths

KW - symmetric Schroder paths

UR - http://www.fpsac.org/

M3 - Paper

ER -

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