×

Matchings in complete bipartite graphs and the \(r\)-Lah numbers. (English) Zbl 1524.05242

Summary: We give a graph theoretic interpretation of \(r\)-Lah numbers, namely, we show that the \(r\)-Lah number \(\lfloor{\substack{n\\k}}\rfloor_{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\geq 1\)). 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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C31 Graph polynomials
05A18 Partitions of sets
05A15 Exact enumeration problems, generating functions
05A19 Combinatorial identities, bijective combinatorics
11B73 Bell and Stirling numbers
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Belbachir, H.; Belkhir, A., Cross recurrence relations for r-Lah numbers, Ars Comb., 110, 199-203 (2013) · Zbl 1313.11034
[2] Belbachir, H.; Bousbaa, I. E., Combinatorial identities for the r-Lah numbers, Ars Comb., 115, 453-458 (2014) · Zbl 1340.05010
[3] Broder, A. Z., The r-Stirling numbers, Discrete Math., 49, 241-259 (1984) · Zbl 0535.05006 · doi:10.1016/0012-365X(84)90161-4
[4] Carlitz, L., Weighted Stirling numbers of the first and second kind, I. Fibonacci Q., 18, 147-162 (1980) · Zbl 0428.05003
[5] Cheon, G-S; Jung, J-H, r-Whitney numbers of Dowling lattices, Discrete Math., 312, 2337-2348 (2012) · Zbl 1246.05009 · doi:10.1016/j.disc.2012.04.001
[6] El-Desouky, B. S.; Shiha, F. A., A q-analogue of \(\overline \alpha \)-Whitney numbers, Appl. Anal. Discrete Math., 12, 178-191 (2018) · Zbl 1488.05024 · doi:10.2298/AADM1801178E
[7] Engbers, J.; Galvin, D.; Hilyard, J., Combinatorially interpreting generalized Stirling numbers, Eur. J. Comb., 43, 32-54 (2015) · Zbl 1301.05027 · doi:10.1016/j.ejc.2014.07.002
[8] E. Gyimesi: The r-Dowling-Lah polynomials. Mediterr. J. Math. 18 (2021), Article ID 136, 16 pages. · Zbl 1487.11023
[9] Gyimesi, E.; Nyul, G., A note on combinatorial subspaces and r-Stirling numbers, Util. Math., 105, 137-139 (2017) · Zbl 1430.11034
[10] Gyimesi, E.; Nyul, G., New combinatorial interpretations of r-Whitney and r-Whitney-Lah numbers, Discrete Appl. Math., 255, 222-233 (2019) · Zbl 1459.11071 · doi:10.1016/j.dam.2018.08.020
[11] Lah, I., A new kind of numbers and its application in the actuarial mathematics, Inst. Actuários Portug., Bol., 9, 7-15 (1954) · Zbl 0055.37902
[12] Lah, I., Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik, Mitt.-Bl. Math. Statistik, 7, 203-212 (1955) · Zbl 0066.11801
[13] Lovász, L., Combinatorial Problems and Exercises (1993), Amsterdam: North-Holland, Amsterdam · Zbl 0785.05001
[14] Lovász, L.; Plummer, M. D., Matching Theory.Annals of Discrete Mathematics 29 (1986), Amsterdam: North-Holland, Amsterdam · Zbl 0618.05001
[15] Merris, R., The p-Stirling numbers, Turk. J. Math., 24, 379-399 (2000) · Zbl 0970.05003
[16] Mező, I.; Ramírez, J. L., The linear algebra of the r-Whitney matrices, Integral Transforms Spec. Funct., 26, 213-225 (2015) · Zbl 1371.11062 · doi:10.1080/10652469.2014.984180
[17] Mihoubi, M.; Rahmani, M., The partial r-Bell polynomials, Afr. Mat., 28, 1167-1183 (2017) · Zbl 1387.05018 · doi:10.1007/s13370-017-0510-z
[18] Nyul, G.; Rácz, G., The r-Lah numbers, Discrete Math., 338, 1660-1666 (2015) · Zbl 1315.05018 · doi:10.1016/j.disc.2014.03.029
[19] Nyul, G.; Rácz, G., Sums of r-Lah numbers and r-Lah polynomials, Ars Math. Contemp., 18, 211-222 (2020) · Zbl 1464.05013 · doi:10.26493/1855-3974.1793.c4d
[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. · 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. · Zbl 1355.05047
[22] Shattuck, M., A generalized recurrence formula for Stirling numbers and related sequences, Notes Number Theory Discrete Math., 21, 74-80 (2015) · Zbl 1346.05015
[23] Shattuck, M., Generalizations of Bell number formulas of Spivey and Mezö, Filomat, 30, 2683-2694 (2016) · Zbl 1462.05039 · doi:10.2298/FIL1610683S
[24] Shattuck, M., Generalized r-Lah numbers, Proc. Indian Acad. Sci., Math. Sci., 126, 461-478 (2016) · Zbl 1351.05033 · doi:10.1007/s12044-016-0309-0
[25] Shattuck, M., Some formulas for the restricted r-Lah numbers, Ann. Math. Inform., 49, 123-140 (2018) · Zbl 1424.11062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.