Enumeration of Matchings in Complete q-ary Trees

Mathematical notes. 2022. Vol. 111. No. 3. P. 398–406.

Kuz’min N., Malyshev D.

We study the asymptotic behavior of the parameters m(Tq,n) and im(Tq,n), that equal the number of matchings and independent matchings in a complete q-ary tree Tq,n of height n. We show that, for any q ≥ 2, there exists a bq > 1 such that, as n → +∞, the following asymptotic equality holds: $m(T_{q,n})\thicksim (\frac{1+\sqrt{1+4\cdot q}}{2})^{-\frac{1}{q-1}} \cdot(b_q)^{q^n}$ . We also show that, for any q ∈ {1, 2, 3}, there exist numbers $a_q$ and $b_q>1$ such that $im(T_{q,n})\thicksim a_q\cdot (b_q)^{q^{n}}$ as n → +∞, and also, for any sufficiently large q, there exist numbers $a^{1}_q\neq a^{2}_q$ and $b_q>1$ such that, as n → +∞, the following asymptotic equalities hold: $im(T_{q,3n})\thicksim a^{1}_q\cdot (b_q)^{q^{3n}}$, $im(T_{q,3n+1})\thicksim a^{2}_q\cdot (b_q)^{q^{3n+1}},im(T_{q,3n+2})\thicksim a^{1}_q\cdot (b_q)^{q^{3n+2}}$.

Keywords: паросочетание, полное q-арное дерево, предельная теорема, limit theorem, matching, независимое паросочетание, independent matching, complete q-ary tree