Matchings in complete bipartite graphs and the r -Lah numbers

Gábor Nyul; Gabriella Rácz

Czechoslovak Mathematical Journal (2021)

  • Volume: 71, Issue: 4, page 947-959
  • ISSN: 0011-4642

Abstract

top
We give a graph theoretic interpretation of r -Lah numbers, namely, we show that the r -Lah number n 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 + 2 r - 1 ( 0 ≤ k ≤ n , r ≥ 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.

How to cite

top

Nyul, Gábor, and Rácz, Gabriella. "Matchings in complete bipartite graphs and the $r$-Lah numbers." Czechoslovak Mathematical Journal 71.4 (2021): 947-959. <http://eudml.org/doc/297979>.

@article{Nyul2021,
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\le k\le n$, $r\ge 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.},
author = {Nyul, Gábor, Rácz, Gabriella},
journal = {Czechoslovak Mathematical Journal},
keywords = {$r$-Lah number; number of matchings; complete bipartite graph; $r$-Stirling number of the second kind},
language = {eng},
number = {4},
pages = {947-959},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Matchings in complete bipartite graphs and the $r$-Lah numbers},
url = {http://eudml.org/doc/297979},
volume = {71},
year = {2021},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 71
IS - 4
SP - 947
EP - 959
AB - 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\le k\le n$, $r\ge 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.
LA - eng
KW - $r$-Lah number; number of matchings; complete bipartite graph; $r$-Stirling number of the second kind
UR - http://eudml.org/doc/297979
ER -

References

top
  1. Belbachir, H., Belkhir, A., Cross recurrence relations for r -Lah numbers, Ars Comb. 110 (2013), 199-203. (2013) Zbl1313.11034MR3100323
  2. Belbachir, H., Bousbaa, I. E., Combinatorial identities for the r -Lah numbers, Ars Comb. 115 (2014), 453-458. (2014) Zbl1340.05010MR3236192
  3. Broder, A. Z., 10.1016/0012-365X(84)90161-4, Discrete Math. 49 (1984), 241-259. (1984) Zbl0535.05006MR0743795DOI10.1016/0012-365X(84)90161-4
  4. Carlitz, L., Weighted Stirling numbers of the first and second kind. I, Fibonacci Q. 18 (1980), 147-162. (1980) Zbl0428.05003MR0570168
  5. Cheon, G.-S., Jung, J.-H., 10.1016/j.disc.2012.04.001, Discrete Math. 312 (2012), 2337-2348. (2012) Zbl1246.05009MR2926106DOI10.1016/j.disc.2012.04.001
  6. El-Desouky, B. S., Shiha, F. A., 10.2298/AADM1801178E, Appl. Anal. Discrete Math. 12 (2018), 178-191. (2018) MR3800372DOI10.2298/AADM1801178E
  7. Engbers, J., Galvin, D., Hilyard, J., 10.1016/j.ejc.2014.07.002, Eur. J. Comb. 43 (2015), 32-54. (2015) Zbl1301.05027MR3266282DOI10.1016/j.ejc.2014.07.002
  8. Gyimesi, E., 10.1007/s00009-020-01669-2, Mediterr. J. Math. 18 (2021), Article ID 136, 16 pages. (2021) DOI10.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. (2017) Zbl1430.11034MR3727889
  10. Gyimesi, E., Nyul, G., 10.1016/j.dam.2018.08.020, Discrete Appl. Math. 255 (2019), 222-233. (2019) Zbl07027138MR3926342DOI10.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 (1954), 7-15. (1954) Zbl0055.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. (1955) Zbl0066.11801MR0074435
  13. Lovász, L., 10.1016/c2009-0-09109-0, North-Holland, Amsterdam (1993). (1993) Zbl0785.05001MR1265492DOI10.1016/c2009-0-09109-0
  14. Lovász, L., Plummer, M. D., 10.1016/s0304-0208(08)x7172-5, Annals of Discrete Mathematics 29. North-Holland Mathematics Studies 121. North-Holland, Amsterdam (1986). (1986) Zbl0618.05001MR0859549DOI10.1016/s0304-0208(08)x7172-5
  15. Merris, R., The p -Stirling numbers, Turk. J. Math. 24 (2000), 379-399. (2000) Zbl0970.05003MR1803821
  16. Mező, I., Ramírez, J. L., 10.1080/10652469.2014.984180, Integral Transforms Spec. Funct. 26 (2015), 213-225. (2015) Zbl1371.11062MR3293040DOI10.1080/10652469.2014.984180
  17. Mihoubi, M., Rahmani, M., 10.1007/s13370-017-0510-z, Afr. Mat. 28 (2017), 1167-1183. (2017) Zbl1387.05018MR3714591DOI10.1007/s13370-017-0510-z
  18. Nyul, G., Rácz, G., 10.1016/j.disc.2014.03.029, Discrete Math. 338 (2015), 1660-1666. (2015) Zbl1315.05018MR3351685DOI10.1016/j.disc.2014.03.029
  19. Nyul, G., Rácz, G., 10.26493/1855-3974.1793.c4d, Ars Math. Contemp. 18 (2020), 211-222. (2020) Zbl07349763MR4165846DOI10.26493/1855-3974.1793.c4d
  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. (2016) Zbl1342.05015MR3514549
  21. Schlosser, M. J., Yoo, M., 10.37236/6121, Electron. J. Comb. 24 (2017), Article ID P1.31, 47 pages. (2017) Zbl1355.05047MR3625908DOI10.37236/6121
  22. Shattuck, M., A generalized recurrence formula for Stirling numbers and related sequences, Notes Number Theory Discrete Math. 21 (2015), 74-80. (2015) Zbl1346.05015
  23. Shattuck, M., 10.2298/FIL1610683S, Filomat 30 (2016), 2683-2694. (2016) Zbl06749914MR3583394DOI10.2298/FIL1610683S
  24. Shattuck, M., 10.1007/s12044-016-0309-0, Proc. Indian Acad. Sci., Math. Sci. 126 (2016), 461-478. (2016) Zbl1351.05033MR3568246DOI10.1007/s12044-016-0309-0
  25. Shattuck, M., 10.33039/ami.2018.11.001, Ann. Math. Inform. 49 (2018), 123-140. (2018) Zbl1424.11062MR3900900DOI10.33039/ami.2018.11.001

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.