Symmetric Schröder paths and restricted involutions

W.M.B. Dukes, Eva Deng, Toufik Mansour, Susan Wu

Research output: Contribution to journalArticle

Abstract

Let Ak be the set of permutations in the symmetric group Sk with prefix 12. This paper concerns the enumeration of involutions which avoid the set of patterns Ak. We present a bijection between symmetric Schroder paths of length $2n and involutions of length n+1 avoiding mathcalA4. Statistics such as the number of right-to-left maxima and fixed points of the involution correspond to the number of steps in the symmetric Schroder path of a particular type. For each k> 2 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.
LanguageEnglish
Pages4108-4115
Number of pages8
JournalDiscrete Mathematics
Volume309
Issue number12
DOIs
Publication statusPublished - 2009

Fingerprint

Involution
Statistics
Path
Fixed point
Prefix
Bijection
Subsequence
Symmetric group
Enumeration
Generating Function
Permutation

Keywords

  • Schröder paths
  • restricted involutions
  • mathematics

Cite this

Dukes, W. M. B., Deng, E., Mansour, T., & Wu, S. (2009). Symmetric Schröder paths and restricted involutions. Discrete Mathematics, 309(12), 4108-4115. https://doi.org/10.1016/j.disc.2008.12.011
Dukes, W.M.B. ; Deng, Eva ; Mansour, Toufik ; Wu, Susan. / Symmetric Schröder paths and restricted involutions. In: Discrete Mathematics. 2009 ; Vol. 309, No. 12. pp. 4108-4115.
@article{b233855ba9b7407eb193d7b30c98341a,
title = "Symmetric Schr{\"o}der paths and restricted involutions",
abstract = "Let Ak be the set of permutations in the symmetric group Sk with prefix 12. This paper concerns the enumeration of involutions which avoid the set of patterns Ak. We present a bijection between symmetric Schroder paths of length $2n and involutions of length n+1 avoiding mathcalA4. Statistics such as the number of right-to-left maxima and fixed points of the involution correspond to the number of steps in the symmetric Schroder path of a particular type. For each k> 2 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 = "Schr{\"o}der paths , restricted involutions, mathematics",
author = "W.M.B. Dukes and Eva Deng and Toufik Mansour and Susan Wu",
year = "2009",
doi = "10.1016/j.disc.2008.12.011",
language = "English",
volume = "309",
pages = "4108--4115",
journal = "Discrete Mathematics",
issn = "0012-365X",
number = "12",

}

Dukes, WMB, Deng, E, Mansour, T & Wu, S 2009, 'Symmetric Schröder paths and restricted involutions' Discrete Mathematics, vol. 309, no. 12, pp. 4108-4115. https://doi.org/10.1016/j.disc.2008.12.011

Symmetric Schröder paths and restricted involutions. / Dukes, W.M.B.; Deng, Eva; Mansour, Toufik; Wu, Susan.

In: Discrete Mathematics, Vol. 309, No. 12, 2009, p. 4108-4115.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Symmetric Schröder paths and restricted involutions

AU - Dukes, W.M.B.

AU - Deng, Eva

AU - Mansour, Toufik

AU - Wu, Susan

PY - 2009

Y1 - 2009

N2 - Let Ak be the set of permutations in the symmetric group Sk with prefix 12. This paper concerns the enumeration of involutions which avoid the set of patterns Ak. We present a bijection between symmetric Schroder paths of length $2n and involutions of length n+1 avoiding mathcalA4. Statistics such as the number of right-to-left maxima and fixed points of the involution correspond to the number of steps in the symmetric Schroder path of a particular type. For each k> 2 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 - Let Ak be the set of permutations in the symmetric group Sk with prefix 12. This paper concerns the enumeration of involutions which avoid the set of patterns Ak. We present a bijection between symmetric Schroder paths of length $2n and involutions of length n+1 avoiding mathcalA4. Statistics such as the number of right-to-left maxima and fixed points of the involution correspond to the number of steps in the symmetric Schroder path of a particular type. For each k> 2 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 - Schröder paths

KW - restricted involutions

KW - mathematics

UR - http://arxiv.org/abs/0810.5189

U2 - 10.1016/j.disc.2008.12.011

DO - 10.1016/j.disc.2008.12.011

M3 - Article

VL - 309

SP - 4108

EP - 4115

JO - Discrete Mathematics

T2 - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 12

ER -