Annals of Combinatorics 1 (1997) 313-327

A Combinatorial Interpretation of the Seidel Generation of q-derangement Numbers

Robert J. Clarke, Guo-Niu Han, and Jiang Zeng

Pure Mathematics Department, University of Adelaide, Adelaide, South Australia 5005

I.R.M.A., Université Louis-Pasteur et C.N.R.S., 67084 Strasbourg Cedex, France

Institut Girard Desargues, Université Claude Bernard (Lyon I) F-69622 Villeurbanne Cedex, France

Received September 15, 1997

AMS Subject Classification: 05A15, 05A30

Abstract. In [8] Dumont and Randrianarivony have given several combinatorial interpretations for the coefficients of the Euler-Seidel matrix associated with n!. In this paper we consider a q-analogue of their results, which leads to the discovery of a new Mahonian statistic maf on the symmetric group. We then give new proofs and generalizations of some results of Gessel and Reutenauer [12] and Wachs [17].

Keywords: Mahonian statistics, permutations, q-derangement numbers, Seidel matrices


1.  G. Andrews, The Theory of Partitions, Addison-Wesley Publishing Company, 1976.

2.  M. Aigner, Combinatorial Theory, Springer-Verlag, Berin, 1979.

3.  W.Y.C. Chen, The skew, relative, and classical derangements, Discrete Math. 160 (1996) 235–239.

4.  W.Y.C. Chen and G.-C. Rota, q-Analogs of the inclusion-exclusion principle and permutations with restricted position, Discrete Math. 104 91992) 7–12.

5.  R.Clarke and D. Foata, Eulerian calculus, II: an extension of Han's fundamental transformation, Europ. J. Combin. 1 (1995) 221–252.

6.  J. Désarménien and M.L. Wachs, Descent classes of permutationswith a giben number of fixed points, J. Combin. Theory Ser. A 64 (1993) 311–328.

7.  D. Dumont, Matrices d'Euler-Seidel, Séminaire Lotharingien de Combinatoire B 05C (1981),

8.  D. Dumont and A. Randrianarivony, Dérangements et nombers de Genocchi, Discrete Math. 132 (1994) 37–49.

9.  D. Dumont and G.Viennot, A Combinatorial interpretation of the Seidel generation of Genocchi numbers, Ann. Discrete Math. 6 (1980) 77–87.

10.  D. Foata, Rearrangements of words, In: Combinatorics on Words, Encyclopedia of Mathematics, Vol. 17, M. Lothaire, Ed., Addison-Wesley, Reading, MA, 1981, pp. 184–212.

11.  G. Gasper and M. Rahman, Basic Hypergeometric Series, Cambridge University Press, 1990.

12.  I. Gessel and C.Reutenauer, Counting Permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64 (1993) 189–215.

13.  G.-N. Han, Unetransformation fondamentale sur les rérrangements de mots, Adv. Math. 105 (1994) 26–41.

14.  P.A. MacMahon, The indices of permutations and the derivation thereform of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math. 35 (1913) 314–321.

15.  D.P. Roselle, Permutattions by number of rises and successions, Proc. Amer. Math. Soc. 19 (1968) 8–16.

16.  R. Stanley, Enumerative Combinatorics I, Cambridge University Press, 1997.

17.  M. Wachs, On q-derangement numbers, Proc. Amer.math.Soc. 106 (1989) 273–278.

Get the LaTex | DVI | PS file of this abstract.