Geodesic
Matchings in complete bipartite graphs and the $r$-Lah numbers
Czechoslovak Mathematical Journal, Tome 71 (2021) no. 4, pp. 947-959
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2021.0148-20
Classification : 05A19, 05C31, 05C70, 11B73
Keywords: $r$-Lah number; number of matchings; complete bipartite graph; $r$-Stirling number of the second kind 
@article{10_21136_CMJ_2021_0148_20,
     author = {Nyul, G\'abor and R\'acz, Gabriella},
     title = {Matchings in complete bipartite graphs and the $r${-Lah} numbers},
     journal = {Czechoslovak Mathematical Journal},
     pages = {947--959},
     year = {2021},
     volume = {71},
     number = {4},
     doi = {10.21136/CMJ.2021.0148-20},
     mrnumber = {4339102},
     zbl = {07442465},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0148-20/}
}
TY  - JOUR
AU  - Nyul, Gábor
AU  - Rácz, Gabriella
TI  - Matchings in complete bipartite graphs and the $r$-Lah numbers
JO  - Czechoslovak Mathematical Journal
PY  - 2021
SP  - 947
EP  - 959
VL  - 71
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0148-20/
DO  - 10.21136/CMJ.2021.0148-20
LA  - en
ID  - 10_21136_CMJ_2021_0148_20
ER  - 
%0 Journal Article
%A Nyul, Gábor
%A Rácz, Gabriella
%T Matchings in complete bipartite graphs and the $r$-Lah numbers
%J Czechoslovak Mathematical Journal
%D 2021
%P 947-959
%V 71
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0148-20/
%R 10.21136/CMJ.2021.0148-20
%G en
%F 10_21136_CMJ_2021_0148_20
Nyul, Gábor; Rácz, Gabriella. Matchings in complete bipartite graphs and the $r$-Lah numbers. Czechoslovak Mathematical Journal, Tome 71 (2021) no. 4, pp. 947-959. doi: 10.21136/CMJ.2021.0148-20

[1] Belbachir, H., Belkhir, A.: Cross recurrence relations for $r$-Lah numbers. Ars Comb. 110 (2013), 199-203. | MR | JFM

[2] Belbachir, H., Bousbaa, I. E.: Combinatorial identities for the $r$-Lah numbers. Ars Comb. 115 (2014), 453-458. | MR | JFM

[3] Broder, A. Z.: The $r$-Stirling numbers. Discrete Math. 49 (1984), 241-259. | DOI | MR | JFM

[4] Carlitz, L.: Weighted Stirling numbers of the first and second kind. I. Fibonacci Q. 18 (1980), 147-162. | MR | JFM

[5] Cheon, G.-S., Jung, J.-H.: $r$-Whitney numbers of Dowling lattices. Discrete Math. 312 (2012), 2337-2348. | DOI | MR | JFM

[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 | MR

[7] Engbers, J., Galvin, D., Hilyard, J.: Combinatorially interpreting generalized Stirling numbers. Eur. J. Comb. 43 (2015), 32-54. | DOI | MR | JFM

[8] Gyimesi, E.: The $r$-Dowling-Lah polynomials. Mediterr. J. Math. 18 (2021), Article ID 136, 16 pages. | DOI

[9] Gyimesi, E., Nyul, G.: A note on combinatorial subspaces and $r$-Stirling numbers. Util. Math. 105 (2017), 137-139. | MR | JFM

[10] Gyimesi, E., Nyul, G.: New combinatorial interpretations of $r$-Whitney and $r$-Whitney- Lah numbers. Discrete Appl. Math. 255 (2019), 222-233. | DOI | MR | JFM

[11] Lah, I.: A new kind of numbers and its application in the actuarial mathematics. Inst. Actuários Portug., Bol. 9 (1954), 7-15. | JFM

[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 | JFM

[13] Lovász, L.: Combinatorial Problems and Exercises. North-Holland, Amsterdam (1993). | DOI | MR | JFM

[14] Lovász, L., Plummer, M. D.: Matching Theory. Annals of Discrete Mathematics 29. North-Holland Mathematics Studies 121. North-Holland, Amsterdam (1986). | DOI | MR | JFM

[15] Merris, R.: The $p$-Stirling numbers. Turk. J. Math. 24 (2000), 379-399. | MR | JFM

[16] Mező, I., Ramírez, J. L.: The linear algebra of the $r$-Whitney matrices. Integral Transforms Spec. Funct. 26 (2015), 213-225. | DOI | MR | JFM

[17] Mihoubi, M., Rahmani, M.: The partial $r$-Bell polynomials. Afr. Mat. 28 (2017), 1167-1183. | DOI | MR | JFM

[18] Nyul, G., Rácz, G.: The $r$-Lah numbers. Discrete Math. 338 (2015), 1660-1666. | DOI | MR | JFM

[19] Nyul, G., Rácz, G.: Sums of $r$-Lah numbers and $r$-Lah polynomials. Ars Math. Contemp. 18 (2020), 211-222. | DOI | MR | JFM

[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 | JFM

[21] Schlosser, M. J., Yoo, M.: Elliptic rook and file numbers. Electron. J. Comb. 24 (2017), Article ID P1.31, 47 pages. | DOI | MR | JFM

[22] Shattuck, M.: A generalized recurrence formula for Stirling numbers and related sequences. Notes Number Theory Discrete Math. 21 (2015), 74-80. | JFM

[23] Shattuck, M.: Generalizations of Bell number formulas of Spivey and Mező. Filomat 30 (2016), 2683-2694. | DOI | MR | JFM

[24] Shattuck, M.: Generalized $r$-Lah numbers. Proc. Indian Acad. Sci., Math. Sci. 126 (2016), 461-478. | DOI | MR | JFM

[25] Shattuck, M.: Some formulas for the restricted $r$-Lah numbers. Ann. Math. Inform. 49 (2018), 123-140. | DOI | MR | JFM

Cité par Sources :