Toufik Mansour ; Alek Vainshtein - Avoiding maximal parabolic subgroups of S_k

dmtcs:276 - Discrete Mathematics & Theoretical Computer Science, January 1, 2000, Vol. 4 no. 1 - https://doi.org/10.46298/dmtcs.276
Avoiding maximal parabolic subgroups of S_kArticle

Authors: Toufik Mansour ORCID1,2; Alek Vainshtein 1,2

  • 1 Department of Computer Science [Haifa]
  • 2 Department of Mathematics [Haïfa]

We find an explicit expression for the generating function of the number of permutations in S_n avoiding a subgroup of S_k generated by all but one simple transpositions. The generating function turns out to be rational, and its denominator is a rook polynomial for a rectangular board.

https://doi.org/10.46298/dmtcs.276
Source: HAL:hal-00958946v1
Volume: Vol. 4 no. 1
Published on: January 1, 2000
Imported on: March 26, 2015
Keywords: permutations,forbidden patterns,parabolic subgroups,Laguerre polynomials,rook polynomials,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 360 times.
This article's PDF has been downloaded 398 times.