Riv. Mat. Univ. Parma, Vol. 11, No. 2, 2020

Margherita Maria Ferrari [a], Emanuele Munarini [b] and Norma Zagaglia Salvi [b]

Some combinatorial properties of the generalized derangement numbers

Pages: 217-249
Received: 9 April 2019
Accepted in revised form: 27 August 2020
Mathematics Subject Classification (2010): Primary 05A19, 05A15; Secondary 11B73, 11B83.
Keywords: species, permutation, derangement, arrangement, enriched partition, enriched partition with no singleton block, rencontres polynomial, Stirling number, Bell number.
Authors address:
[a]: Department of Mathematics and Statistics, University of South Florida, 4202 E. Fowler Avenue, Tampa, FL 33620, USA
[b]: Dipartimento di Matematica, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133 Milano, Italy

This research was partially supported by the NSF CCF-1526485 and DMS-1800443, the NIH R01GM109459-01, the Southeast Center for Mathematics and Biology (an NSF-Simons Research Center for Mathematics of Complex Biological Systems) under NSF DMS-1764406 and Simons Foundation 594594 (first author).

Full Text (PDF)

Abstract: In this paper, we give a simple description of the \(m\)-widened permutations (generalized \(m\)-permutations) and the \(m\)-widened derangements (generalized \(m\)-derangements) in terms of ordinary permutations and derangements with a suitable constraint. This approach allows us to give a natural combinatorial interpretation of the generalized derangement numbers and the generalized rencontres polynomials in terms of species of structures. Finally, we obtain some formulas relating the generalized derangement numbers with the \(r\)-Bell numbers. In particular, we give an extension of the Clarke-Sved identity.

References
[1]
U. Abel, Some new identities for derangement numbers, Fibonacci Quart. 56 (2018), 313-318. MR3884914
[2]
M. Abramson, A note on permanents, Canad. Math. Bull. 14 (1971), 1-4. MR0292858
[3]
S. H. Assaf, Cyclic derangements, Electron. J. Combin. 17 (2010), Paper 163. MR2745716
[4]
J.-L. Baril and V. Vajnovszki, Gray code for derangements, Discrete Appl. Math. 140 (2004), 207-221. MR2064117
[5]
G. Bhatnagar, In praise of an elementary identity of Euler, Electron. J. Combin. 18 (2011), Paper 13. MR2811063
[6]
G. Bhatnagar, Analogues of a Fibonacci-Lucas identity, Fibonacci Quart. 54 (2016), 166-171. MR3512836
[7]
F. Beggas, M. M. Ferrari and N. Zagaglia Salvi, Combinatorial interpretations and enumeration of particular bijections, Riv. Mat. Univ. Parma 8 (2017), 161-169. MR3765662
[8]
F. Bergeron, G. Labelle and P. Leroux, Introduction to the theory of species of structures, Université du Québec à Montréal, 2008.   Article
[9]
F. Brenti, Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc. 108 (1990), 1133-1141. MR0993741
[10]
K. S. Briggs and J. B. Remmel, A \(p,q\)-analogue of the generalized derangement numbers, Ann. Comb. 13 (2009), 1-25. MR2529717
[11]
A. Z. Broder, The \(r\)-Stirling numbers, Discrete Math. 49 (1984), 241-259. MR0743795
[12]
R. A. Brualdi and H. J. Ryser, Combinatorial matrix theory, Encyclopedia Math. Appl., 39, Cambridge University Press, Cambridge, 1991. MR1130611
[13]
P. J. Cameron, Lectures on derangements, Pretty Structures Workshop, Institut Henri Poincaré, Paris, 2011.   Article
[14]
S. Capparelli, A. Del Fra and V. Pepe, Widened derangements and generalized Laguerre polynomials, Ramanujan J. 49 (2019), 269-286. MR3949070
[15]
S. Capparelli, M. M. Ferrari, E. Munarini and N. Zagaglia Salvi, A generalization of the "Problème des Rencontres", J. Integer Seq. 21 (2018), Art. 18.2.8. MR3779777
[16]
L. Carlitz, The number of derangements of a sequence with given specification, Fibonacci Quart. 16 (1978), 255-258. MR0509279
[17]
L. Chao, P. DesJarlais and J. L. Leonard, A binomial identity, via derangements, Math. Gaz. 89 (2005), 268-270.   https://doi.org/10.1017/S0025557200177800
[18]
W. Y. C. Chen and G.-C. Rota, \(q\)-analogs of the inclusion-exclusion principle and permutations with restricted position, Discrete Math. 104 (1992), 7-22. MR1171787
[19]
C.-O. Chow, On derangement polynomials of type B, Sém. Lothar. Combin. 55 (2005/07), Art. B55b. MR2223025
[20]
C.-O. Chow, On derangement polynomials of type B, II, J. Combin. Theory Ser. A 116 (2009), 816-830. MR2513636
[21]
R. J. Clarke, G.-N. Han and J. Zeng, A combinatorial interpretation of the Seidel generation of \(q\)-derangement numbers, Ann. Comb. 1 (1997), 313-327. MR1630814
[22]
R. J. Clarke and M. Sved, Derangements and Bell numbers, Math. Mag. 66 (1993), 299-303. MR1251443
[23]
L. Comtet, Advanced Combinatorics, Reidel Publishing, Dordrecht, 1974. MR0460128
[24]
J. Désarménien, Une autre interprétation du nombre des dérangements, Sém. Lothar. Combin. 8 (1983), Art. B08b. %%URL https://elibm.org/article/10009626
[25]
J. Désarménien, Distribution de l'indice majeur réduit sur les dérangements, Sém. Lothar. Combin. 32 (1994), Art. B32a.   Article
[26]
J. Désarménien and M. Wachs, Descentes des dérangements et mots circulaires, Sém. Lothar. Combin. 19 (1988), Art. B19a.   Article
[27]
E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, European J. Combin. 31 (2010), 1404-1409. MR2644428
[28]
D. Dumont and A. Randrianarivony, Dérangements et nombres de Genocchi, Discrete Math. 132 (1990), 37-49. MR1297370
[29]
L. Euler, Calcul de la probabilité dans le jeu de rencontre, Mém. Acad. Sci. Berlin 7 (1753), 255-270; Opera omnia (1) 7 (1923), 11-25.   Article
[30]
L. Euler, Solutio quaestionis curiosae ex doctrina combinationum, Mém. Acad. Sci. St. Pétersbourg 3 (1811), 57-64; Opera omnia (1) 7 (1923), 435-448.   Article
[31]
S. Even and J. Gillis, Derangements and Laguerre polynomials, Math. Proc. Cambridge Philos. Soc. 79 (1976), 135-143. MR0392590
[32]
P. Feinsilver and J. McSorley, Zeons, permanents, the Johnson scheme, and generalized derangements, Int. J. Comb. (2011), Art. ID 539030. MR2796186
[33]
M. M. Ferrari and E. Munarini, Decomposition of some Hankel matrices generated by the generalized rencontres polynomials, Linear Algebra Appl. 567 (2019), 180-201. MR3900729
[34]
D. Foata and D. Zeilberger, Laguerre polynomials, weighted derangements, and positivity, SIAM J. Discrete Math. 1 (1988), 425-433. MR0968850
[35]
A. M. Garsia and J. Remmel, A combinatorial interpretation of \(q\)-derangements and \(q\)-Laguerre numbers, European J. Combin. 1 (1980), 47-59. MR0576766
[36]
I. M. Gessel, A coloring problem, Amer. Math. Monthly 98 (1991), 530-533. MR1109577
[37]
G. Gordon and E. McMahon, Moving faces to other places: facet derangements, Amer. Math. Monthly 117 (2010), 865-880. MR2759360
[38]
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley Publishing, Reading, MA, 1989. MR1001562
[39]
M. Hassani, Derangements and applications, J. Integer Seq. 6 (2003), Art. 03.1.2. MR1971432
[40]
M. Hassani, Cycles in graphs and derangements, Math. Gaz. 88 (2004), 123-126.   https://doi.org/10.1017/S0025557200174443
[41]
Y. He and J. Pan, Some recursion formulae for the number of derangements and Bell numbers, J. Math. Res. Appl. 36 (2016), 15-22. MR3468948
[42]
D. M. Jackson, Laguerre polynomials and derangements, Math. Proc. Cambridge Philos. Soc. 80 (1976), 213-214. MR0409204
[43]
A. Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), 1-82. MR0633783
[44]
T. Kim, D. S. Kim, G.-W. Jang and J. Kwon, A note on some identities of derangement polynomials, J. Inequal. Appl. (2018), Paper No. 40. MR3764699
[45]
D. Kim and J. Zeng, A new decomposition of derangements, J. Combin. Theory Ser. A 96 (2001), 192-198. MR185579
[46]
L. L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, Adv. in Appl. Math. 38 (2007), 542-560. MR2311051
[47]
P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea Publishing , New York, 1960. MR0141605
[48]
I. Martinjak and D. Stanić, A short combinatorial proof of derangement identity, Elem. Math. 73 (2018), 29-33. MR3746490
[49]
I. Mező, The \(r\)-Bell numbers, J. Integer Seq. 14 (2011), Art. 11.1.1. MR2772025
[50]
I. Mező and J. L. Ramírez, Divisibility properties of the \(r\)-Bell numbers and polynomials, J. Number Theory 177 (2017), 136-152. MR3629238
[51]
I. Mező, J. L. Ramírez and C.-Y. Wang, On generalized derangements and some orthogonal polynomials, Integers 19 (2019), Paper No. A6. MR3901618
[52]
P. R. Montmort, Essay d'Analyse sur les Jeux de Hazard, Paris, 1708, (Second edition, 1713).   Article
[53]
H. Moshtagh, A note on k-derangements, Appl. Math. E-Notes 18 (2018), 167-169. MR3850119
[54]
E. Munarini, Combinatorial identities for Appell polynomials, Appl. Anal. Discrete Math. 12 (2018), 362-388. MR3875327
[55]
E. Munarini, Callan-like identities, Online J. Anal. Comb. 14 (2019). MR4020137
[56]
S. G. Penrice, Derangements, permanents, and Christmas presents, Amer. Math. Monthly 98 (1991), 617-620. MR1121314
[57]
C. Radoux, Déterminant de Hankel construit sur des polynômes liés aux nombres de dérangements, European J. Combin. 12 (1991), 327-329. MR1120419
[58]
F. Rakotondrajao, \(k\)-fixed-points-permutations, Pure Math. Appl. (PU.M.A.) 17 (2006), 165-173. MR2380355
[59]
F. Rakotondrajao, On Eulers difference table, in: Proc. Formal Power Series and Algebraic Combinatorics (FPSAC) 07, Tianjin, China (2007).
[60]
J. B. Remmel, A note on a recursion for the number of derangements, European J. Combin. 4 (1983), 371-374. MR0743160
[61]
J. Riordan, An introduction to combinatorial analysis, John Wiley & Sons, New York, 1958. MR0096594
[62]
S. Roman, The umbral calculus, Academic Press, New York, 1984. MR0741185
[63]
H. J. Ryser, Combinatorial mathematics, John Wiley & Sons, New York, 1963. MR0150048
[64]
G. R. Sanchis, Swapping hats: A generalization of Montmort's problem, Math. Mag. 71 (1998), 53-57. MR1573290
[65]
N. J. A. Sloane, The on-line encyclopedia of integer sequences, electronically published at http://oeis.org/ .
[66]
R. P. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997. MR1442260
[67]
Y. Sun, X. Wu and J. Zhuang, Congruences on the Bell polynomials and the derangement polynomials, J. Number Theory 133 (2013), 1564-1571. MR3007122
[68]
Z.-W. Sun and D. Zagier, On a curious property of Bell numbers, Bull. Aust. Math. Soc. 84 (2011), 153-158. MR2817669
[69]
L. Takács, The problem of coincidences, Arch. Hist. Exact Sci. 21 (1979/80), 229-244. MR0575716
[70]
R. Vidunas, Counting derangements and Nash equilibria, Ann. Comb. 21 (2017), 131-152. MR3613449
[71]
M. L. Wachs, On \(q\)-derangement numbers, Proc. Amer. Math. Soc. 106 (1989), 273-278. MR0937015
[72]
C. Wang, P. Miska and I. Mező, The \(r\)-derangement numbers, Discrete Math. 340 (2017), 1681-1692. MR3634139
[73]
H. S. Wilf, A bijection in the theory of derangements, Math. Mag. 57 (1984), 37-40. DOI: 10.2307/2690295
[74]
E. M. Wright, Arithmetical properties of Euler's rencontre number, J. London Math. Soc. (2) 4 (1971/72), 437-442. MR0294235
[75]
J. Zeng, Weighted derangements and the linearization coefficients of orthogonal Sheffer polynomials, Proc. London Math. Soc. 65 (1992), 1-22. MR1162485
[76]
X. Zhang, On \(q\)-derangement polynomials, in: Combinatorics and graph theory '95, Vol. 1 (Hefei, 1995), World Sci. Publishing, River Edge, NJ, 1995, 462-465. MR1476230
[77]
X.-D. Zhang, On the spiral property of the \(q\)-derangement numbers, Discrete Math. 159 (1996), 295-298. MR1415308

Home Riv.Mat.Univ.Parma