Geodesic
Matchings in complete bipartite graphs and the $r$-Lah numbers
Czechoslovak Mathematical Journal, Tome 71 (2021) no. 4, pp. 947-959

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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},
     publisher = {mathdoc},
     volume = {71},
     number = {4},
     year = {2021},
     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
PB  - mathdoc
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
%I mathdoc
%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

Cité par Sources :