Efficient Weighted Counting of Multi-Set Derangements

Efficient Weighted Counting of Multiset Derangements
By Shalosh B. Ekhad and Doron Zeilberger
.pdf .tex journal version

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

Dedicated to Mourad E.-H.Ismail (b. April 27, 1944) on his 80th birthday, with friendship and admiration
[ Appeared (Arab. J. Math. (2025). https://doi.org/10.1007/s40065-025-00524-0) in the Arabian Journal of Mathematics (Speical issue in honor of Mourad Ismail, guest-edited by Erik Koelink and Mahmoud Annaby)]
On-line before print (volume and page tbd)

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.

[Acknowledgment: The authors wish to thank guest-editor Erik Koelink for help in dealing with the journal)]

Maple package

Mourad.txt, a Maple package that does weighted counting of Multiset Derangements.

Sample Input and Output for Mourad.txt

If you want to see the linear recurrences for the weight-enumerators, according to the number of cycles of π permutations of a set of the form
A₁ Union ... Union A_n
where the A_i are pairwise disjoint and each has k members, and for each member x of A_i , π(x) is NOT in A_i, for k from 1 to 10
The input file yields the output file

If you want to see the linear recurrences for the weight-enumerators, according to the number of cycles of π permutations of a set of the form
A₁ Union ... Union A_n
where the A_i are pairwise disjoint and each has k members, and for each member x of A_i , π(x) is NOT in A_i, for k from 1 to 7, and for each case, the first 30 terms, as well as the case n=100, followed by the average, variance, and scaled moments for the latter case
The input file yields the output file

If you want to see the weight-enumerator according to the number of cycles of derangements of a standard deck of cards
The input file yields the output file

Articles of Doron Zeilberger
Doron Zeilberger's Home Page