Séminaire Lotharingien de Combinatoire, B08c (1984) 9 pp. [Formerly : Publ. I.R.M.A. Strasbourg, 1984, 229/S–08, p. 17–25.]

WEIGHTED DERANGEMENTS

AND LAGUERRE POLYNOMIALS

BY

Dominique FOATA AND Doron ZEILBERGER

1. Introduction. — One of the harbingers of the current combinatorization of the theory of special functions was a remarkable result of GILLIS and EVEN [7] that gave a certain combinatorial interpretation to the linearization coefficients of the simple Laguerre polynomials L_{n}(x). Let (L_{n}^{(α)}(x)) be the sequence of the (general) Laguerre polynomials that may be defined by their generating function

(1.1)  ∑_{n=0}^{∞} L_{n}^{(α)}(x)u^{n} = (1 − u)^{−α−1} exp \frac{−xu}{1 − u},

the simple Laguerre polynomials being defined by L_{n}(x) = L_{n}^{0}(x) (α = 0). Furthermore, for each positive integer m and each sequence (n_{1}, …, n_{m}) of nonnegative integers let

(1.2) A(n_{1}, …, n_{m}; α) = (−1)^{n_{1}+···+n_{m}} ∫_{0}^{∞}(∏_{i=1}^{m} L_{n_{i}}^{(α)}(x)) x^{α}e^{−x} dx

and

(1.3)  I(n_{1}, …, n_{m}; α) = \frac{1}{Γ(α + 1)}n_{1}! … n_{m}! A(n_{1}, …, n_{m}; α).

Then GILLIS and EVEN [7] found a combinatorial interpretation for I(n_{1}, …, n_{m}; 0) (α = 0) and deduced from that interpretation the fact that I(n_{1}, …, n_{m}; 0) was positive. The positivity property was immediately reproved by ASKEY and his followers [1, 2, 3, 8] by means of analytical methods and reincluded in a more general special function set-up. As they noticed, the generating function (1.1) yields the identity : (1.4)

∑ A(n_{1}, …, n_{m}; α)x_{1}^{n_{1}} … x_{m}^{n_{m}} = \frac{Γ(α + 1)}{(1 − σ_{2} − 2σ_{3} − ⋯ − (m − 1)σ_{m})^{α+1}} ,

D. FOATA AND D. ZEILBERGER

where n_{1}, …, n_{m} runs over all nonnegative integers and σ_{j} denotes the j-th elementary symmetric function in x_{1}, …, x_{m}. As it was shown by ASKEY and his coauthors, the positivity of I(n_{1}, …, n_{m}; α) is an immediate consequence of (1.4) and it holds for α > −1. In [1, p. 857–858] the authors were very close to finding a combinatorial interpretation of I(n_{1}, …, n_{m}; α) for an arbitrary α. It is the purpose of this paper to provide one by taking up again the combinatorial model introduced by GILLIS and EVEN [7] and “α-extending” it. Let P(n_{1}, …, n_{m}) be the set of permutations on the n_{1} + ⋯ + n_{m} elements

a_{1,1}, …, a_{1,n_{1}}; …; a_{m,1}, …, a_{m,n_{m}}

and denote by D(n_{1}, …, n_{m}) the subset of P(n_{1}, …, n_{m}) consisting of what we will call (a_{1}, …, a_{m})-derangements. These are permutations where no element is allowed to go to one of its kind ; in other words, columns of the form

\begin{matrix}a_{1,i} & … & a_{m,i} \\ a_{1,j} & … & a_{m,j} \end{matrix}

are forbidden in the two-line representation of the permutation. The following identity is due to GILLIS and EVENS [7] :

(1.5)  I(n_{1}, …, n_{m}; 0) = card D(n_{1}, …, n_{m}).

In order to have an extension for any α introduce for each permutation π its number of cycles cyc π and define its weight by

(1.6)  w(π) = (α + 1)^{cyc π}.

The polynomial

D(n_{1}, …, n_{m}; α) = ∑_{π} w(π) (π ∈ D(n_{1}, …, n_{m}))

reduces to card D(n_{1}, …, n_{m}) when α = 0. Our α-analog of the Gillis-Even result now reads :

Theorem 1. — For each indeterminate α one has :

(1.7)  I(n_{1}, …, n_{m}; α) = D(n_{1}, …, n_{m}; α).

As all the weights in D(n_{1}, …, n_{m}; α) are nonnegative whenever α > −1, then the forementioned theorem implies that I(n_{1}, …, n_{m}; α) is also nonnegative, as was proved by ASKEY et al. [1, 2].

WEIGHTED DERANGEMENTS

We give two proofs of THEOREM 1. The first one is based on the combinatorial interpretation of the Laguerre polynomials. The product (1.3) is expanded and the various terms interpreted in terms of generating polynomials for permutations and injections (see sections 2 and 3). The second one relies on an β-analog of the celebrated MACMAHON’s Master Theorem [9, p. 97]. This β-analog has an interest of its own and will be discussed in section 4. The second proof is then completed in section 5.

2. Cycles. — We will need two results that are fundamental in the current combinatorial interpretation of special functions. First, the generating function for the set P(n) of all the permutations on n elements by number of cycles is given by (see, e.g., [10, p. 78]) (2.1)

w(P(n)) = ∑_{π} w(π) = (α+1)_{n} = (α+1)(α+2) … (α+n) (π ∈ P(n)).

Let 1 ≤ k ≤ n and S be a (n − k)-element subset of the n-element [n]. The set of injections from S into [n] will be denoted by Inj(S, n). An injection from S to [n] consists of a (possibly empty) collection of cycles within S and some paths that wander in S, but terminate at a point outside S. Similarly, denote by cyc π the number of cycles of π and define its weight by w(π) = (α + 1)^{cyc π}.

For example, if S = {1, 2, 3, 4, 5, 6} and n = 9, then (1, 3), (2), 4 → 5 → 7, 6 → 8 is an injection with weight (α + 1)^{2}.

The result analogous to (1.1) reads (see [6, lemma 2.1]) : if card S = n − k, then

(2.2) w(Inj(S, n)) = ∑_{π} w(π) = (α + 1 + k)_{n−k}  (π ∈ Inj(S, n)).

3. Proof of theorem 1. — By the definition of the Laguerre polynomials

n_{i}! L_{n_{i}}^{(α)}(x) = ∑_{k_{i}=0}^{n_{i}}(−1)^{k_{i}} \binom{n_{i}}{k_{i}}(α + 1 + k_{i})_{n_{i}−k_{i}} x^{k_{i}} (i = 1, …, m).

In (1.2) and (1.3) expand each Laguerre polynomial and integrate term by term using the fact that (1/Γ(α + 1)) ∫_{0}^{∞} e^{−x}x^{n+α} dx = (α + 1)_{n}. This leads to :

(3.1) I(n_{1}, …, n_{m}; α)

= ∑_{k_{1}=0}^{n_{1}}⋯ ∑_{k_{m}=0}^{n_{m}}(α + 1)_{k_{1}+···+k_{m}} ∏_{i=1}^{m}(−1)^{n_{i}−k_{i}} \binom{n_{i}}{k_{i}}(α + 1 + k_{i})_{n_{i}−k_{i}}.

Consider now any permutation in P(n_{1}, …, n_{m}) and write it in cycle form. An element will be called incestuous, if it is sent to one of its own kind. Denote by Inc π the set of all incestuous elements of π.

For example, in the permutation belonging to P(4, 5, 5)

(a_{1}b_{1}b_{2}c_{3}a_{2})(c_{2}c_{1}b_{3}a_{3})(c_{4}b_{4}a_{4}c_{5})

the elements b_{1}, a_{2}, c_{2}, c_{5} are the incestuous elements.

Now call marked permutation an ordered pair (π, S) with π a permutation and S a subset of Inc π and denote by M(n_{1}, …, n_{m}) the set of marked permutations.

For example,

(a_{1}\overline{b_{1}}b_{2}c_{3}a_{2})(\overline{c_{2}}c_{1}b_{3}a_{3})(c_{4}b_{4}a_{4}\overline{c_{5}})

is the marked permutation where the incestuous elements b_{1}, c_{2}, c_{5} are marked (S = {b_{1}, c_{2}, c_{5}}) while the incestuous element a_{2} is not marked.

Define the weight of each marked permutation (π, S) by

w′(π, S) = (−1)^{card S}(α + 1)^{cyc π}

and consider the generating polynomial for marked permutations :

M(n_{1}, …, n_{m}; α) = ∑_{π} w′(π) (π ∈ M(n_{1}, …, n_{m})).

This generating polynomial will be computed in two different ways. One of these ways yields

(3.2)  M(n_{1}, …, n_{m}; α) = D(n_{1}, …, n_{m}; α).

The other way will give :

(3.3)  M(n_{1}, …, n_{m}; α) = I(n_{1}, …, n_{m}; α).

Consider the following weight preserving sign changing involution on marked permutations. Look at the first incestuous element. If it is marked, unmark it ; if it is unmarked, mark it. Of course, the number of cycles of the permutation does not change (since there is no change in the underlying permutation !). Only the parity of the number of marks changes, reversing the sign of the weight. Accordingly, all the terms in M(n_{1}, …, n_{m}; α) corresponding to permutations with incestuous elements can be arranged in mutually cancelling pairs and their sum is therefore zero. All that remains in M(n_{1}, …, n_{m}; α) are the terms corresponding to those marked permutations (π, S) containing no incestuous elements and so S = ∅.

But those marked permutations are simply the pairs (π, ∅) with π ∈ D(n_{1}, …, n_{m}) and they satisfy : w′(π, ∅) = w(π). Therefore (3.2) holds.

Now compute M(n_{1}, …, n_{m}; α) in a different way. For each i = 1, …, m let S_{i} be a certain subset of {a_{i,1}, …, a_{i,n_{i}}} of cardinality n_{i}−k_{i} and denote by M(S) the subset of M(n_{1}, …, n_{n}) consisting of marked permutations (π, S) with S = S_{1}∪⋯∪S_{m}. Also let P(S) the set of all π in P(n_{1}, …, n_{m}) such that (π, S) ∈ M(S). Clearly,

(3.4)  w′(M(S)) = (−1)^{n_{1}−k_{1}+···+n_{m}−k_{m}}w(P(S)).

Lemma. — One has

(3.5)  w(P(S)) = (α + 1)_{k_{1}+···+k_{m}} ∏_{i=1}^{m}(α + 1 + k_{i})_{n_{i}−k_{i}}.

Proof. — From (2.1) and (2.2) it follows that the right-hand side of (3.5) is the generating function for the product

P(k_{1}, …, k_{m}) × ∏_{i=1}^{m} Inj(S_{i}, n_{i})

by w. To prove the lemma it then suffices to construct a w-weight preserving bijection π ↦ (π_{1}, …, π_{m}, σ) of P(S) onto that product. Write π in cycle form. Then in each cycle of π delete all the elements of S = S_{1} ∪ ⋯ ∪ S_{m}. What remains is a permutation written in cycle form. Call it σ.

To get π_{i} take all the cycles of π consisting only of elements of S_{i}. Take also the connected portions of S_{i} lying in other cycles. Doing this will result in a certain number of paths that wander through S_{i} but terminate in an element not in S_{i}.

Clearly, σ belongs to P(k_{1}, …, k_{m}) and each π_{i} is an injection of S_{i} into {a_{i,1}, …, a_{i,n_{i}}}. Moreover, the total number of cycles of σ, π_{1}, …, π_{m} is equal to cyc π. Thus, the mapping is w-preserving. The reverse construction is immediate.

Example. — Take

n_{1} = 6  n_{2} = 6  n_{3} = 6
k_{1} = 3  k_{2} = 3  k_{3} = 3
S_{1} = {a_{1}, a_{2}, a_{3}} S_{2} = {b_{1}, b_{2}, b_{3}} S_{3} = {c_{1}, c_{2}, c_{3}}
π = (a_{1}a_{2})(a_{4}b_{1}b_{5}a_{5}a_{3})(b_{2}b_{4}c_{1}c_{4}c_{3}c_{2}c_{6})(c_{5}a_{6})(b_{3})(b_{6})

Then

σ = (a_{4}b_{5}a_{5})(b_{4}c_{4}c_{6})(c_{5}c_{6})(b_{6})
π_{1} = (a_{1}a_{2}), a_{3} → a_{4}
π_{2} = (b_{3}), b_{1} → b_{5}, b_{2} → b_{4}
π_{3} = c_{1} → c_{4}, c_{3} → c_{2} → c_{6}

It follows from (3.4) and (3.5) that

w′(M(S)) = (−1)^{n_{1}−k_{1}+···+n_{m}−k_{m}}(α + 1)_{k_{1}+···+k_{m}} ∏_{i=1}^{m}(α + 1 + k_{i})_{n_{i}−k_{i}}.

Hence

M(n_{1}, …, n_{m}; α) = ∑ w′(M(S))

= ∑_{k_{1}=0}^{n_{1}}⋯ ∑_{k_{m}=0}^{n_{m}} ∏_{i=1}^{m} \binom{n_{i}}{k_{i}} ∑ w′(M(S))

= ∑_{k_{1}=0}^{n_{1}}⋯ ∑_{k_{m}=0}^{n_{m}}(α + 1)_{k_{1}+···+k_{m}}

× ∏_{i=1}^{m}(−1)^{n_{i}−k_{i}} \binom{n_{i}}{k_{i}}(α + 1 + k_{i})_{n_{i}−k_{i}},

which is the expression found for I(n_{1}, …, n_{m}; α) in (3.1). Therefore, (3.3) is proved and also THEOREM 1.

4. The β-analog of the MacMahon Master Theorem. — Let D be the determinant det(δ_{ij} − b(i, j)x_{j}) (1 ≤ i, j ≤ m). The MacMahon Master Theorem asserts that the coefficient of x_{1}^{n_{1}} … x_{m}^{n_{m}} in the expansion of D^{−1} is equal to the coefficient of x_{1}^{n_{1}} … x_{m}^{n_{m}} in the product

(4.1) (b(1, 1)x_{1} +⋯+b(1, m)x_{m})^{n_{1}} … (b(m, 1)x_{1} +⋯+b(m, m)x_{m})^{n_{m}}.

It will be convenient to restate this statement in a slightly different form. Let R(n_{1}, …, n_{m}) denote the set of all the rearrangements

r = r(1, 1) … r(1, n_{1}) … r(m, 1) … r(m, n_{m})

of the word 1^{n_{1}} … m^{n_{m}} and let

v(r) = ∏_{i,j} b(i, r(i, j)) (1 ≤ i ≤ m; 1 ≤ j ≤ n_{i}).

Clearly, the coefficient of x_{1}^{n_{1}} … x_{m}^{n_{m}} in (4.1) is equal to the sum of all the v(r) with r running over all the rearrangements of 1^{n_{1}} … m^{n_{m}}.

Next, consider a permutation π belonging to P(n_{1}, …, n_{m}) (defined in section 1). If π sends (i, j) over (i′, j′), write i′ = cπ(i, j). Furthermore, define

v(π) = ∏_{i,j} b(i, cπ(i, j)) (1 ≤ i ≤ m; 1 ≤ j ≤ n_{i}).

To each rearrangement r in R(n_{1}, …, n_{m}) there correspond exactly n_{1}! … n_{m}! permutations π in P(n_{1}, …, n_{m}) with the property that v(π) = v(r). Therefore, the coefficient of x_{1}^{n_{1}} … x_{m}^{n_{m}} in (4.1) is also equal to

(4.2)  n_{1}! … n_{m}! ∑_{π} v(π)  (π ∈ P(n_{1}, …, n_{m}).

The MacMahon Master identity can then be restated as

(4.3)  ∑ \frac{x_{1}^{n_{1}}}{n_{1}!} … \frac{x_{m}^{n_{m}}}{n_{m}!} v(P(n_{1}, …, n_{m})) = D^{−1}.

Next define the β-weight v(β; π) of each permutation π in P(n_{1}, …, n_{m}) by

v(β; π) = β^{cyc π}v(π).

Theorem (β-analog of the MacMahon Master Theorem). — The following identity holds :

(4.4)  ∑ \frac{x_{1}^{n_{1}}}{n_{1}!} … \frac{x_{m}^{n_{m}}}{n_{m}!} v(β; P(n_{1}, …, n_{m})) = D^{−β}.

Proof. — Consider the partitional complex (see, e.g., [4, 5]) of the permutations and denote by CP(n_{1}, …, n_{m}) the subset of the connected permutations in P(n_{1}, …, n_{m}). As the weight v(β; ·) is multiplicative [4, 5], the following identity holds :

(4.5) ∑ \frac{x_{1}^{n_{1}}}{n_{1}!} … \frac{x_{m}^{n_{m}}}{n_{m}!} v(β; P(n_{1}, …, n_{m}))

= exp ∑ \frac{x_{1}^{n_{1}}}{n_{1}!} … \frac{x_{m}^{n_{m}}}{n_{m}!} v(β; CP(n_{1}, …, n_{m})).

From (4.3) and (4.5) with β = 1

∑ \frac{x_{1}^{n_{1}}}{n_{1}!} … \frac{x_{m}^{n_{m}}}{n_{m}!} v(CP(n_{1}, …, n_{m})) = −Log D.

But v(β; π) = βv(π) for every connected permutation, so that

∑ \frac{x_{1}^{n_{1}}}{n_{1}!} … \frac{x_{m}^{n_{m}}}{n_{m}!} v(β; CP(n_{1}, …, n_{m})) = −βLog D,

and finally (4.4) holds because of (4.5).

5. Second proof of theorem 1. — As was noted by ASKEY [1, 2], (1.4) is an immediate consequence of (1.1). Rewriting (1.4) for α = 0 using GILLIS-EVEN’s result (1.5) yields : (5.1)

∑ card D(n_{1}, …, n_{m})\frac{x_{1}^{n_{1}}}{n_{1}!} … \frac{x_{m}^{n_{m}}}{n_{m}!} = (1 − σ_{2} − 2σ_{3} − ⋯ − (m − 1)σ_{m})^{−1}.

Take again the v-weight of section 4 with b(i, j) = δ_{ij}. Then,

(5.2)  card D(n_{1}, …, n_{m}) = v(P(n_{1}, …, n_{m})).

Thus for this particular v identity (4.4) holds with β = α + 1 and

D = (1 − σ_{2} − 2σ_{3} − ⋯ (m − 1)σ_{m}).

On the account of (1.2), (1.3), (1.4) and (4.4) with this particular weight v we conclude that (1.7) also holds.

REFERENCES

[1] ASKEY (Richard) and ISMAIL (Mourad E.H.). — Permutation problems and special functions, Canad. J. Math., t. 28, 1976, p. 853–874.

[2] ASKEY (Richard), ISMAIL (Mourad E.H.) and KOORNWINDER (T.). — Weighted permutation problems and Laguerre polynomials, J. Combinatorial Theory, Ser. A, t. 25, 1978, p. 277–287.

[3] ASKEY (Richard) and GASPER (G.). — Convolution structures for Laguerre polynomials, J. d’Anal. Math., t. 31, 1977, p. 46–48.

[4] FOATA (Dominique). — La série génératrice exponentielle dans les problèmes d’énumération. — Montréal, Presses de l’Université de Montréal, 1974.

[5] FOATA (Dominique) et SCH^{}ÜTZENBERGER (Marcel-Paul). — Théorie géométrique des polynômes eulériens. — Berlin, Springer-Verlag, 1970 (Lecture Notes in Math., 138).

[6] FOATA (Dominique) and STREHL (Volker). — Combinatorics of Laguerre polynomials, Enumeration and Design [Waterloo. June–July 1982 : D.M. Jackson and S.A. Vanstone, eds.], p. 123–140. — Toronto, Academic Press, 1984.

[7] GILLIS (J.) and EVEN (S.). — Derangements and Laguerre polynomials, Proc. Cambridge Phil. Soc., t. 79, 1976, p. 135–143.

[8] ISMAIL (Mourad E.H.) and TAMHANKAR (M.V.). — A combinatorial approach to some positivity problems, S.I.A.M. J. Math. Anal., t. 10, 1979, p. 478–485.

[9] MACMAHON (Percy Alexander). — Combinatory Analysis, vol. 1. — Cambridge, Univ. Press, 1915. (Reprinted by Chelsea, New York, 1955).

[10] RIORDAN (John). — An Introduction to Combinatorial Analysis. — New York, John Wiley, 1959.

The present paper has been completed and updated to become :

Dominique Foata and Doron Zeilberger, Laguerre polynomials, weighted derangements and positivity, SIAM J. Discrete Math., vol. 1, 1988, p. 425– 433.

Dominique Foata, Département de mathématique, Université Louis-Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France.

and

Doron Zeilberger, Department of Mathematics, Drexel University, Philadelphia, Pennsylvania 19104, U.S.A. now at the address : Temple University, Philadelphia, Pennsylvania 19122, U.S.A.