Séminaire Lotharingien de Combinatoire, B59d (2008), 15 pp.

Chak-On Chow

Counting Multiderangements by Excedances

Abstract. We consider in this work the enumeration of multiderangements of a multiset n={1n1,2n2,...,mnm} by the number of excedances. We prove several properties, including the invariance under permutations of {n1,n2,...,nm}, the symmetry, the recurrence relation, the real-rootedness, and a combinatorial expansion, of the generating function dn(x) of multiderangements by excedances, thus generalizing the corresponding results for the classical derangements. By a further extension, the generating function for multipermutations by numbers of excedances and fixed points is also given.

Received: October 8, 2007. Revised: April 28, 2008; May 13, 2008. Accepted: May 18, 2008. Final Version: May 18, 2008.

The following versions are available: