| Title:
|
Matchings in complete bipartite graphs and the $r$-Lah numbers (English) |
| Author:
|
Nyul, Gábor |
| Author:
|
Rácz, Gabriella |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
71 |
| Issue:
|
4 |
| Year:
|
2021 |
| Pages:
|
947-959 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
$r$-Lah number |
| Keyword:
|
number of matchings |
| Keyword:
|
complete bipartite graph |
| Keyword:
|
$r$-Stirling number of the second kind |
| MSC:
|
05A19 |
| MSC:
|
05C31 |
| MSC:
|
05C70 |
| MSC:
|
11B73 |
| idZBL:
|
Zbl 07442465 |
| idMR:
|
MR4339102 |
| DOI:
|
10.21136/CMJ.2021.0148-20 |
| . |
| Date available:
|
2021-11-08T15:56:16Z |
| Last updated:
|
2024-01-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149229 |
| . |
| Reference:
|
[1] Belbachir, H., Belkhir, A.: Cross recurrence relations for $r$-Lah numbers.Ars Comb. 110 (2013), 199-203. Zbl 1313.11034, MR 3100323 |
| Reference:
|
[2] Belbachir, H., Bousbaa, I. E.: Combinatorial identities for the $r$-Lah numbers.Ars Comb. 115 (2014), 453-458. Zbl 1340.05010, MR 3236192 |
| Reference:
|
[3] Broder, A. Z.: The $r$-Stirling numbers.Discrete Math. 49 (1984), 241-259. Zbl 0535.05006, MR 0743795, 10.1016/0012-365X(84)90161-4 |
| Reference:
|
[4] Carlitz, L.: Weighted Stirling numbers of the first and second kind. I.Fibonacci Q. 18 (1980), 147-162. Zbl 0428.05003, MR 0570168 |
| Reference:
|
[5] Cheon, G.-S., Jung, J.-H.: $r$-Whitney numbers of Dowling lattices.Discrete Math. 312 (2012), 2337-2348. Zbl 1246.05009, MR 2926106, 10.1016/j.disc.2012.04.001 |
| Reference:
|
[6] El-Desouky, B. S., Shiha, F. A.: A $q$-analogue of $\bar{\alpha}$-Whitney numbers.Appl. Anal. Discrete Math. 12 (2018), 178-191. MR 3800372, 10.2298/AADM1801178E |
| Reference:
|
[7] Engbers, J., Galvin, D., Hilyard, J.: Combinatorially interpreting generalized Stirling numbers.Eur. J. Comb. 43 (2015), 32-54. Zbl 1301.05027, MR 3266282, 10.1016/j.ejc.2014.07.002 |
| Reference:
|
[8] Gyimesi, E.: The $r$-Dowling-Lah polynomials.Mediterr. J. Math. 18 (2021), Article ID 136, 16 pages. 10.1007/s00009-020-01669-2 |
| Reference:
|
[9] Gyimesi, E., Nyul, G.: A note on combinatorial subspaces and $r$-Stirling numbers.Util. Math. 105 (2017), 137-139. Zbl 1430.11034, MR 3727889 |
| Reference:
|
[10] Gyimesi, E., Nyul, G.: New combinatorial interpretations of $r$-Whitney and $r$-Whitney- Lah numbers.Discrete Appl. Math. 255 (2019), 222-233. Zbl 07027138, MR 3926342, 10.1016/j.dam.2018.08.020 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 0066.11801, MR 0074435 |
| Reference:
|
[13] Lovász, L.: Combinatorial Problems and Exercises.North-Holland, Amsterdam (1993). Zbl 0785.05001, MR 1265492, 10.1016/c2009-0-09109-0 |
| Reference:
|
[14] Lovász, L., Plummer, M. D.: Matching Theory.Annals of Discrete Mathematics 29. North-Holland Mathematics Studies 121. North-Holland, Amsterdam (1986). Zbl 0618.05001, MR 0859549, 10.1016/s0304-0208(08)x7172-5 |
| Reference:
|
[15] Merris, R.: The $p$-Stirling numbers.Turk. J. Math. 24 (2000), 379-399. Zbl 0970.05003, MR 1803821 |
| Reference:
|
[16] Mező, I., Ramírez, J. L.: The linear algebra of the $r$-Whitney matrices.Integral Transforms Spec. Funct. 26 (2015), 213-225. Zbl 1371.11062, MR 3293040, 10.1080/10652469.2014.984180 |
| Reference:
|
[17] Mihoubi, M., Rahmani, M.: The partial $r$-Bell polynomials.Afr. Mat. 28 (2017), 1167-1183. Zbl 1387.05018, MR 3714591, 10.1007/s13370-017-0510-z |
| Reference:
|
[18] Nyul, G., Rácz, G.: The $r$-Lah numbers.Discrete Math. 338 (2015), 1660-1666. Zbl 1315.05018, MR 3351685, 10.1016/j.disc.2014.03.029 |
| Reference:
|
[19] Nyul, G., Rácz, G.: Sums of $r$-Lah numbers and $r$-Lah polynomials.Ars Math. Contemp. 18 (2020), 211-222. Zbl 07349763, MR 4165846, 10.26493/1855-3974.1793.c4d |
| Reference:
|
[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. Zbl 1342.05015, MR 3514549 |
| Reference:
|
[21] Schlosser, M. J., Yoo, M.: Elliptic rook and file numbers.Electron. J. Comb. 24 (2017), Article ID P1.31, 47 pages. Zbl 1355.05047, MR 3625908, 10.37236/6121 |
| Reference:
|
[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 |
| Reference:
|
[23] Shattuck, M.: Generalizations of Bell number formulas of Spivey and Mező.Filomat 30 (2016), 2683-2694. Zbl 06749914, MR 3583394, 10.2298/FIL1610683S |
| Reference:
|
[24] Shattuck, M.: Generalized $r$-Lah numbers.Proc. Indian Acad. Sci., Math. Sci. 126 (2016), 461-478. Zbl 1351.05033, MR 3568246, 10.1007/s12044-016-0309-0 |
| Reference:
|
[25] Shattuck, M.: Some formulas for the restricted $r$-Lah numbers.Ann. Math. Inform. 49 (2018), 123-140. Zbl 1424.11062, MR 3900900, 10.33039/ami.2018.11.001 |
| . |
