Geodesic
Enumeration of Matchings in Complete $q$-ary Trees
Matematičeskie zametki, Tome 111 (2022) no. 3, pp. 393-402.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study the asymptotic behavior of the parameters $m(T_{q,n})$ and $im(T_{q,n})$, that equal the number of matchings and independent matchings in a complete $q$-ary tree $T_{q,n}$ of height $n$. We show that, for any $q\ge 2$, there exists a $b_q>1$ such that, as $n\to+\infty$, the following asymptotic equality holds: $$ m(T_{q,n})\sim\biggl(\frac{1+\sqrt{1+4\cdot q}}2\,\biggr)^{-1/(q-1)}\cdot(b_q)^{q^n}. $$ We also show that, for any $q\in \{1,2,3\}$, there exist numbers $a'_q$ and $b'_q>1$ such that $im(T_{q,n})\sim a'_q\cdot (b'_q)^{q^{n}}$ as $n\to+\infty$, and also, for any sufficiently large $q$, there exist numbers $a^{1}_q\ne a^{2}_q$ and $b'_q>1$ such that, as $n\to+\infty$, the following asymptotic equalities hold: \begin{gather*} im(T_{q,3n})\sim a^{1}_q\cdot (b'_q)^{q^{3n}}, \\ im(T_{q,3n+1})\sim a^{2}_q\cdot (b'_q)^{q^{3n+1}},\qquad im(T_{q,3n+2})\sim a^{1}_q\cdot (b'_q)^{q^{3n+2}}. \end{gather*}
Keywords: limit theorem, matching, independent matching, complete $q$-ary tree. 
@article{MZM_2022_111_3_a5,
     author = {N. A. Kuz'min and D. S. Malyshev},
     title = {Enumeration of {Matchings} in {Complete} $q$-ary {Trees}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {393--402},
     publisher = {mathdoc},
     volume = {111},
     number = {3},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2022_111_3_a5/}
}
TY  - JOUR
AU  - N. A. Kuz'min
AU  - D. S. Malyshev
TI  - Enumeration of Matchings in Complete $q$-ary Trees
JO  - Matematičeskie zametki
PY  - 2022
SP  - 393
EP  - 402
VL  - 111
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2022_111_3_a5/
LA  - ru
ID  - MZM_2022_111_3_a5
ER  - 
%0 Journal Article
%A N. A. Kuz'min
%A D. S. Malyshev
%T Enumeration of Matchings in Complete $q$-ary Trees
%J Matematičeskie zametki
%D 2022
%P 393-402
%V 111
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2022_111_3_a5/
%G ru
%F MZM_2022_111_3_a5
N. A. Kuz'min; D. S. Malyshev. Enumeration of Matchings in Complete $q$-ary Trees. Matematičeskie zametki, Tome 111 (2022) no. 3, pp. 393-402. http://geodesic.mathdoc.fr/item/MZM_2022_111_3_a5/

[1] A. D. Korshunov, A. A. Sapozhenko, “O chisle dvoichnykh kodov s rasstoyaniem 2”, Problemy kibernetiki, 40 (1983), 111–130 | MR | Zbl

[2] N. J. Kalkin, H. S. Wilf, “The number of independent sets in a grid graph”, SIAM J. Discrete Math., 11:1 (1997), 54–60 | DOI | MR

[3] P. Kirschenhofer, H. Prodinger, R. Tichy, “Fibonacci numbers of graphs II”, Fibonacci Quart., 21:3 (1983), 219–229 | MR | Zbl

[4] A. B. Dainyak, “O chisle nezavisimykh mnozhestv v polnykh $q$-arnykh derevyakh”, Uch. zap. Kazanskogo gos. un-ta. Ser. fiz.-matem. nauki, 151:2 (2009), 59–64 | Zbl

[5] D. S. Taletskii, D. S. Malyshev, “O kolichestve maksimalnykh nezavisimykh mnozhestv v polnykh $q$-arnykh derevyakh”, Diskret. matem., 28:4 (2016), 139–149 | DOI | MR

[6] D. S. Taletskii, “O svoistvakh resheniya rekurrentnogo uravneniya, perechislyayuschego maksimalnye nezavisimye mnozhestva v polnykh derevyakh”, Zhurnal SVMO, 20:1 (2018), 46–54 | DOI | Zbl

[7] P. W. Kasteleyn, “The statistics of dimers on a lattice”, Physica, 27:12 (1961), 1209–1225 | DOI | Zbl