RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 2022 Volume 111, Issue 3, Pages 393–402 (Mi mzm13094)

Enumeration of Matchings in Complete $q$-ary Trees

N. A. Kuz'minab, D. S. Malyshevab

a National Research University "Higher School of Economics", Nizhny Novgorod Branch
b National Research Lobachevsky State University of Nizhny Novgorod

Abstract: 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.

UDC: 519.17

Received: 03.04.2021

DOI: 10.4213/mzm13094


 English version:
Mathematical Notes, 2022, 111:3, 398–406

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024