Efficient Weighted Counting of Multiset Derangements

Shalosh B. EKHAD and Doron ZEILBERGER

Dedicated to Mourad El-Houssieny ISMAIL (born April 27, 1944), with friendship and

admiration

Abstract: We use the Almkvist-Zeilberger algorithm, combined with a weighted version of the Even-Gillis Laguerre integral due to Foata and Zeilberger, in order to efficiently compute weight enumerators of multiset derangements according to the number of cycles. The present paper is inspired by important previous work by Mourad Ismail and his collaborators, done in the late 1970s, but still useful after all these years.

Multiset Derangements

The (generalized) Laguerre polynomials, L_{k}^{(α)}(x), are defined as follows:

L_{k}^{(α)}(x) := ∑_{i=0}^{n}(−1)^{i} \frac{(α + i + 1)(α + i + 2) … (α + n)}{i!(n − i)!} x^{i} .

Let A_{1}, A_{2}, …, A_{n} be n pairwise-disjoint sets of cardinalities k_{1}, …, k_{n} respectively. A permutation π of A := A_{1}∪…∪A_{n} is a multiset derangement if for every 1 ≤ i ≤ n, whenever x ∈ A_{i}, π(x) ∉ A_{i}. Let D(k_{1}, …, k_{n}) be the set of such multiset derangements.

As usual, for any finite set S, let |S| denote its number of elements.

Shimon Even and Joe Gillis [EvG] (see also [As], [G], and [Z]) proved that

|D(k_{1}, …, k_{n})| = (−1)^{k_{1}+...+k_{n}} (∏_{i=1}^{n} k_{i}!) ∫_{0}^{∞} (∏_{i=1}^{n} L_{k_{i}}^{(0)}(x)) e^{−x} dx .  (1)

Comment: Usually the elements of each A_{i} are identified, and the formula then does not have (∏_{i=1}^{n} k_{i}!) in front, but for the purpose of the present paper, as was done in [FZ], we have k_{1}+…+k_{n} distinct elements, all preserving their individuality.

For a permutation π, let cyc(π) denote its number of cycles. For example cyc(1234) = 4, and cyc(2341) = 1. Recall that, famously,

∑_{π∈S_{n}} α^{cyc(π)} = α(α + 1) ⋯ (α + n − 1) .

This is easily proved by considering how to form permutations of {1, ..., n} out of those of {1, ..., n − 1}. Denote the left side by f_{n}(α). Given a permutation of {1, ..., n − 1} we can insert n inside any of the existing cycles, and there are n − 1 ways of doing it, preserving the number of cycles, or else create a brand-new cycle with n alone, increasing the number of cycles by one. Hence f_{n}(α) = ((n − 1) + α)f_{n−1}(α).

Let A(k_{1}, …, k_{n})(α) be the weight enumerator, according to the number of cycles, of the set of multiset derangements, D(k_{1}, …, k_{n}), in other words

A(k_{1}, …, k_{n})(α) := ∑_{π∈D(k_{1},...,k_{n})} α^{cyc(π)} .

In 1988, Dominique Foata and one of us (DZ) [FZ], inspired by the work of Mourad Ismail and his collaborators ([AsIs], [AsIsRa], [AsIsKo]) proved the following α-analog of the Even-Gillis theorem:

A(k_{1}, …, k_{n})(α) = \frac{(−1)^{k_{1}+...+k_{n}}}{(α − 1)!} (∏_{i=1}^{n} k_{i}!) ∫_{0}^{∞} (∏_{i=1}^{n} L_{k_{i}}^{(α−1)}(x)) x^{α−1}e^{−x} dx .  (2)

Note that this is a polynomial of degree (k_{1} + … + k_{n})/2 rather than k_{1} + … + k_{n}, since every cycle is at least of length 2.

In this paper we will focus on efficient computations of many terms of the sequences A(k, k, …, k)(α), where k is repeated n times, for specific (small, and not so small) k, but arbitrarily large n. In other words, our goal is to compute as many as possible terms of the sequences

F_{k}(n)(α) := A(k, …, k)(α) , (k repeated n times) ,

for k = 1, k = 2, etc.

By (2) we have

F_{k}(n)(α) = \frac{(−1)^{kn}k!^{n}}{(α − 1)!} ∫_{0}^{∞}(L_{k}^{(α−1)}(x))^{n}x^{α−1}e^{−x} dx .  (3)

Using the Almkvist-Zeilberger algorithm [AlZ] (see [D] for a lucid and engaging account), one of us (SBE), using our Maple package Mourad.txt, available from the front of this article

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/mourad.html ,

discovered (and proved) the following recurrences for F_{k}(n) = F_{k}(n)(α) for 1 ≤ k ≤ 10. They get increasingly complicated, and we will only state the first two in the body of this paper.

−α (n + 1) F_{1}(n) − (n + 1) F_{1}(n + 1) + F_{1}(n + 2) = 0 .  (4)

4α (2n + 5) (n + 2) (n + 1) (α + 1)^{2} F_{2}(n)
+2 (n + 2) (α + 1) (4α n^{2} + 12αn − 4n^{2} + 7α − 14n − 10) F_{2}(n + 1)
−2 (n + 2) (4αn + 4n^{2} + 8α + 16n + 17) F_{2}(n + 2) + (2n + 3) F_{2}(n + 3) = 0 .  (5)

For linear recurrences for F_{k}(n) for 3 ≤ k ≤ 10 see the output file

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oMourad1.txt .

We observe that the order of the recurrence for F_{k}(n) is k + 1 and its degree in n is \binom{k+1}{2}. These recurrences enable very fast computation of quite a few terms of these sequences. It is all implemented in the already mentioned Maple package Mourad.txt. The direct url of this package is:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/Mourad.txt .

A User’s Manual to the Maple package Mourad.txt To use it first download it to your favorite directory (usually Downloads). Start a Maple worksheet, make sure that the directory is the right one, and then type

read `Mourad.txt` ; .

To get a list of the procedures, type ezra(); . The main procedures are:

• Wder(L,a), that inputs a list of positive integers, L = [k_{1}, …, k_{n}] and implements Equation (2). This is very slow, and should not be used for large L.

• Operk(k,a,n,N), that inputs a positive integer k, and outputs the recurrence operator (where N is the shift operator in n) annihilating the sequence F_{k}(n). These get very complicated for human eyes, but the computer does not mind and it enables a fast computation of many terms.

• SeqkF(k,K,α): inputs a positive integer k and a positive integer K and a symbol α and outputs the first K terms of the sequence of polynomials F_{k}(n) = F_{k}(n)(α). For example, to get the weight enumerator of the set of permutations of a standard deck of cards where no card can wind up at a location that originally was occupied by the same number (1 through 13, where Jack, Queen, and King stand for 11, 12, 13 respectively) but it is OK to have the same suit, type:

SeqkF(4,13,α)[13]; ,

and you would get, in a few seconds, the following polynomial in α of degree 26

626486325682388256883179081695232 α^{26}+
3948815860811007759557670403206807552 α^{25}+
4226160446928101410675933447042193424384 α^{24}+
1829313185198525509532452983498671376039936 α^{23}+
425955227133577312273392421310068029118218240 α^{22}+
61568711382255715699343414832865761752795578368 α^{21}+
6015599331237497842549834616372527226200006852608 α^{20}+
420030513102996289545618495318355347968579239673856 α^{19}+

21779385529606788308065066752435641655566027030790144 α^{18}+

861931009463580565142515454351924475556603802576486400 α^{17}+

26556926811772603306934511893782498309330811792400580608 α^{16}+

646219419386602045907824228576682527851206056554484727808 α^{15}+

12544166147808400841334081628081554018739662394272604225536 α^{14}+

195525408546538912690378251287680488219792943092212919435264 α^{13}+

2455695605166443718371007842011087818790955115435503879454720 α^{12}+

24867048146672227309345666989913796704728810126752820020379648 α^{11}+

202569793911613274182929019082185092261014157201085369153486848 α^{10}+

1320388339665569428585764027609539765653334771119656423470923776 α^{9}+

6825167923093955037138102373992833000704975000443998456569135104 α^{8}+

27602809328921835313793682068121303712142304270099611821308641280 α^{7}+

85647342705993322148148235777401007447932223607159691210985046016 α^{6}+

198159663830900044042641789039253865122617020230065397080602443776 α^{5}+

327547473685724687587188995032714624999930689030717701980120154112 α^{4}+

361148215004517312493645900517444844168859774724070502768740139008 α^{3}+

234426065400514976953417524798811902707109969381695319447196139520 α^{2}+

66394948050946830932484058263644488672722608355067055619597926400 α .

Plugging-in α = 1 and dividing by 4!^{13} (to get derangements where members of the same set are identified) gives you:

1493804444499093354916284290188948031229880469556 ,

agreeing with the title of [EkKZ], that handled the straight, rather than the weighted, enumeration of multiset derangements.

Note that the largest coefficient in the above polynomial is that of a^{3}, hence the mode of the random variable ‘number of cycles’ in a random multi-set derangement of a standard deck is 3. The average happens to be 3.586337835 … while the standard-deviation (the squre-root of the variance) is 1.412546929 …

Acknowledgment: Many thanks to the two anonymous referees for very helpful suggestions and corrections on the first draft.

References

[AlZ] Gert Almkvist and Doron Zeilberger, The method of differentiating under the integral sign, J. Symbolic Computation 10, 571-591 (1990).

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/duis.html .

[As] Richard Askey, “Orthogonal Polynomials and Special Functions”, SIAM, 1975.

[AsIs] R. Askey and M.E.H. Ismail, Permutation problems and special functions, Canad. J. Math. 28 (1976), 853-874.

[AsIsKo] R.Askey, M.E.H. Ismail, and T. Koornwinder, Weighted permutation problems and Laguerre polynomials, J. Comb. Theory (Ser. A.) 25 (1978), 277-287.

[AsIsRa] R.Askey, M.E.H. Ismail, and M.T. Rashed, A derangement problem. Technical report 1522, UW-Madison Mathematics Research Center, June 1975.

[D] Robert Dougherty-Bliss, Integral Recurrences from A to Z, The American Mathematical Monthly 129 (2021), 805-815.

[EkKZ] Shalosh B. Ekhad, Christoph Koutschan, and Doron Zeilberger, There are EXACTLY 1493804444499093354916284290188948031229880469556 ways to derange a standard deck of cards (ignoring suits) [and many other such useful facts], Enumerative Combinatorics and Applications 1 (2021), issue 3, article S2A17.

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multider.html .

[EvG] S. Even and J. Gillis, Derangements and Laguerre polynomials, Math. Proc. Camb. Phil. Soc. 79 (1976), 135-143.

[FZ] Dominique Foata and Doron Zeilberger, Laguerre polynomials, weighted derangements, and positivity, SIAM J. Discrete Mathematics 1 (1988), 425-433.

[G] J. Gillis, The statistics of derangement-a survey, Journal of Statistical Physics 58 (1990),575-578.

[GIO] J. Gillis, M. E. H. Ismail, and T. Offer, An Asymptotic Problem in Derangement Theory, SIAM Journal on Mathematical Analysis 21 (1990), 262-269.

[Z] Doron Zeilberger, How Joe Gillis discovered combinatorial special function theory, Math. Intell. 17(2) (Spring 1995), 65-66.

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/gillis.html

Shalosh B. Ekhad, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ShaloshBEkhad at gmail dot com .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

First version: Jan. 7, 2025 . This version: Jan. 26, 2025.