Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
$r$-Lah number; number of matchings; complete bipartite graph; $r$-Stirling number of the second kind
$r$-Lah number; number of matchings; complete bipartite graph; $r$-Stirling number of the second kind
Summary:
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\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.
References:
[1] Belbachir, H., Belkhir, A.: Cross recurrence relations for $r$-Lah numbers. Ars Comb. 110 (2013), 199-203. MR 3100323 | Zbl 1313.11034
[2] Belbachir, H., Bousbaa, I. E.: Combinatorial identities for the $r$-Lah numbers. Ars Comb. 115 (2014), 453-458. MR 3236192 | Zbl 1340.05010
[3] Broder, A. Z.: The $r$-Stirling numbers. Discrete Math. 49 (1984), 241-259. DOI 10.1016/0012-365X(84)90161-4 | MR 0743795 | Zbl 0535.05006
[4] Carlitz, L.: Weighted Stirling numbers of the first and second kind. I. Fibonacci Q. 18 (1980), 147-162. MR 0570168 | Zbl 0428.05003
[5] Cheon, G.-S., Jung, J.-H.: $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] El-Desouky, B. S., Shiha, F. A.: A $q$-analogue of $\bar{\alpha}$-Whitney numbers. Appl. Anal. Discrete Math. 12 (2018), 178-191. DOI 10.2298/AADM1801178E | MR 3800372
[7] Engbers, J., Galvin, D., Hilyard, J.: 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] Gyimesi, E.: The $r$-Dowling-Lah polynomials. Mediterr. J. Math. 18 (2021), Article ID 136, 16 pages. DOI 10.1007/s00009-020-01669-2
[9] Gyimesi, E., Nyul, G.: A note on combinatorial subspaces and $r$-Stirling numbers. Util. Math. 105 (2017), 137-139. MR 3727889 | Zbl 1430.11034
[10] Gyimesi, E., Nyul, G.: 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] Lah, I.: 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] Lah, I.: Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik. Mitt.-Bl. Math. Statistik 7 (1955), 203-212 German. MR 0074435 | Zbl 0066.11801
[13] Lovász, L.: Combinatorial Problems and Exercises. North-Holland, Amsterdam (1993). DOI 10.1016/c2009-0-09109-0 | MR 1265492 | Zbl 0785.05001
[14] Lovász, L., Plummer, M. D.: 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] Merris, R.: The $p$-Stirling numbers. Turk. J. Math. 24 (2000), 379-399. MR 1803821 | Zbl 0970.05003
[16] Mező, I., Ramírez, J. L.: 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] Mihoubi, M., Rahmani, M.: The partial $r$-Bell polynomials. Afr. Mat. 28 (2017), 1167-1183. DOI 10.1007/s13370-017-0510-z | MR 3714591 | Zbl 1387.05018
[18] Nyul, G., Rácz, G.: The $r$-Lah numbers. Discrete Math. 338 (2015), 1660-1666. DOI 10.1016/j.disc.2014.03.029 | MR 3351685 | Zbl 1315.05018
[19] Nyul, G., Rácz, G.: 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] Ramírez, J. L., Shattuck, M.: 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] Schlosser, M. J., Yoo, M.: 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] Shattuck, M.: A generalized recurrence formula for Stirling numbers and related sequences. Notes Number Theory Discrete Math. 21 (2015), 74-80. Zbl 1346.05015
[23] Shattuck, M.: Generalizations of Bell number formulas of Spivey and Mező. Filomat 30 (2016), 2683-2694. DOI 10.2298/FIL1610683S | MR 3583394 | Zbl 06749914
[24] Shattuck, M.: 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] Shattuck, M.: 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
Search
Partner of
