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