Czechoslovak Mathematical Journal, Vol. 71, No. 4, pp. 947-959, 2021


Matchings in complete bipartite graphs and the $r$-Lah numbers

Gábor Nyul, Gabriella Rácz

Received April 4, 2020.   Published online May 26, 2021.

Abstract:  We give a graph theoretic interpretation of $r$-Lah numbers, namely, we show that the $r$-Lah number ${n \atopwithdelims\lfloor\rfloor k}_r$ counting the number of $r$-partitions of an $(n+r)$-element set into $k+r$ ordered blocks is just equal to the number of matchings consisting of $n-k$ edges in the complete bipartite graph with partite sets of cardinality $n$ and $n+2r-1$ ($0\leq k\leq n$, $r\geq1$). We present five independent proofs including a direct, bijective one. Finally, we close our work with a similar result for $r$-Stirling numbers of the second kind.
Keywords:  $r$-Lah number; number of matchings; complete bipartite graph; $r$-Stirling number of the second kind
Classification MSC:  05C70, 05C31, 05A19, 11B73


References:
[1] H. Belbachir, A. Belkhir: Cross recurrence relations for $r$-Lah numbers. Ars Comb. 110 (2013), 199-203. MR 3100323 | Zbl 1313.11034
[2] H. Belbachir, I. E. Bousbaa: Combinatorial identities for the $r$-Lah numbers. Ars Comb. 115 (2014), 453-458. MR 3236192 | Zbl 1340.05010
[3] A. Z. Broder: The $r$-Stirling numbers. Discrete Math. 49 (1984), 241-259. DOI 10.1016/0012-365X(84)90161-4 | MR 0743795 | Zbl 0535.05006
[4] L. Carlitz: Weighted Stirling numbers of the first and second kind. I. Fibonacci Q. 18 (1980), 147-162. MR 0570168 | Zbl 0428.05003
[5] G.-S. Cheon, J.-H. Jung: $r$-Whitney numbers of Dowling lattices. Discrete Math. 312 (2012), 2337-2348. DOI 10.1016/j.disc.2012.04.001 | MR 2926106 | Zbl 1246.05009
[6] B. S. El-Desouky, F. A. Shiha: A $q$-analogue of $\bar{\alpha}$-Whitney numbers. Appl. Anal. Discrete Math. 12 (2018), 178-191. DOI 10.2298/AADM1801178E | MR 3800372
[7] J. Engbers, D. Galvin, J. Hilyard: Combinatorially interpreting generalized Stirling numbers. Eur. J. Comb. 43 (2015), 32-54. DOI 10.1016/j.ejc.2014.07.002 | MR 3266282 | Zbl 1301.05027
[8] E. Gyimesi: The $r$-Dowling-Lah polynomials. Mediterr. J. Math. 18 (2021), Article ID 136, 16 pages. DOI 10.1007/s00009-020-01669-2
[9] E. Gyimesi, G. Nyul: A note on combinatorial subspaces and $r$-Stirling numbers. Util. Math. 105 (2017), 137-139. MR 3727889 | Zbl 1430.11034
[10] E. Gyimesi, G. Nyul: New combinatorial interpretations of $r$-Whitney and $r$-Whitney-Lah numbers. Discrete Appl. Math. 255 (2019), 222-233. DOI 10.1016/j.dam.2018.08.020 | MR 3926342 | Zbl 07027138
[11] I. Lah: A new kind of numbers and its application in the actuarial mathematics. Inst. Actuários Portug., Bol. 9 (1954), 7-15. Zbl 0055.37902
[12] I. Lah: Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik. Mitt.-Bl. Math. Statistik 7 (1955), 203-212. (In German.) MR 0074435 | Zbl 0066.11801
[13] L. Lovász: Combinatorial Problems and Exercises. North-Holland, Amsterdam (1993). DOI 10.1016/c2009-0-09109-0 | MR 1265492 | Zbl 0785.05001
[14] L. Lovász, M. D. Plummer: Matching Theory. Annals of Discrete Mathematics 29. North-Holland Mathematics Studies 121. North-Holland, Amsterdam (1986). DOI 10.1016/s0304-0208(08)x7172-5 | MR 0859549 | Zbl 0618.05001
[15] R. Merris: The $p$-Stirling numbers. Turk. J. Math. 24 (2000), 379-399. MR 1803821 | Zbl 0970.05003
[16] I. Mező, J. L. Ramírez: The linear algebra of the $r$-Whitney matrices. Integral Transforms Spec. Funct. 26 (2015), 213-225. DOI 10.1080/10652469.2014.984180 | MR 3293040 | Zbl 1371.11062
[17] M. Mihoubi, M. Rahmani: The partial $r$-Bell polynomials. Afr. Mat. 28 (2017), 1167-1183. DOI 10.1007/s13370-017-0510-z | MR 3714591 | Zbl 1387.05018
[18] G. Nyul, G. Rácz: The $r$-Lah numbers. Discrete Math. 338 (2015), 1660-1666. DOI 10.1016/j.disc.2014.03.029 | MR 3351685 | Zbl 1315.05018
[19] G. Nyul, G. Rácz: Sums of $r$-Lah numbers and $r$-Lah polynomials. Ars Math. Contemp. 18 (2020), 211-222. DOI 10.26493/1855-3974.1793.c4d | MR 4165846 | Zbl 07349763
[20] J. L. Ramírez, M. Shattuck: A $(p,q)$-analogue of the $r$-Whitney-Lah numbers. J. Integer Seq. 19 (2016), Article ID 16.5.6., 21 pages. MR 3514549 | Zbl 1342.05015
[21] M. J. Schlosser, M. Yoo: Elliptic rook and file numbers. Electron. J. Comb. 24 (2017), Article ID P1.31, 47 pages. DOI 10.37236/6121 | MR 3625908 | Zbl 1355.05047
[22] M. Shattuck: A generalized recurrence formula for Stirling numbers and related sequences. Notes Number Theory Discrete Math. 21 (2015), 74-80. Zbl 1346.05015
[23] M. Shattuck: Generalizations of Bell number formulas of Spivey and Mező. Filomat 30 (2016), 2683-2694. DOI 10.2298/FIL1610683S | MR 3583394 | Zbl 06749914
[24] M. Shattuck: Generalized $r$-Lah numbers. Proc. Indian Acad. Sci., Math. Sci. 126 (2016), 461-478. DOI 10.1007/s12044-016-0309-0 | MR 3568246 | Zbl 1351.05033
[25] M. Shattuck: Some formulas for the restricted $r$-Lah numbers. Ann. Math. Inform. 49 (2018), 123-140. DOI 10.33039/ami.2018.11.001 | MR 3900900 | Zbl 1424.11062

Affiliations:   Gábor Nyul (corresponding author), Gabriella Rácz, Institute of Mathematics, University of Debrecen, H-4002 Debrecen P.O.Box 400, Hungary, e-mail: gnyul@science.unideb.hu, racz.gabriella@science.unideb.hu


 
PDF available at: