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: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] permutations, forbidden patterns, parabolic subgroups, Laguerre polynomials, rook polynomials

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 613 times.
This article's PDF has been downloaded 512 times.