Discrete Mathematics & Theoretical Computer Science, Vol 4, No 1 (2000)

Font Size:  Small  Medium  Large

Avoiding maximal parabolic subgroups of Sk

Toufik Mansour, Alek Vainshtein

Abstract


We find an explicit expression for the generating function of the number of permutations in Sn avoiding a subgroup of Sk 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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page