Enumeration of Matchings in Complete q-ary Trees

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

Kuz’min N., Малышев Д. С.

В работе исследуется поведение величин $m(T_{q,n})$ и $im(T_{q,n})$ --- количеств паросочетаний и независимых паросочетаний в $T_{q,n}$ --- полном $q$-арном дереве высоты $n$. Показывается, что для любого $q\geq 2$ существует такое $b_q>1$, что при $n\longrightarrow+\infty$ справедлива асимптотика $m(T_{q,n})\thicksim (\frac{1+\sqrt{1+4\cdot q}}{2})^{-\frac{1}{q-1}} \cdot(b_q)^{q^n}$. Показывается также, что для любого $q\in \{1,2,3\}$ существуют числа $a_q$ и $b_q>1$ такие, что~\mbox{$im(T_{q,n})\thicksim a_q\cdot (b_q)^{q^{n}}$} при $n\longrightarrow+\infty$, а также для любого достаточно большого $q$ существуют числа $a^{1}_q\neq a^{2}_q$ и $b_q>1$ такие, что при $n\longrightarrow+\infty$ справедливы асимптотики $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}}$.

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