Перечисление паросочетаний в полных $q$-арных деревьях

В работе исследуется поведение величин $m(T_{q,n})$ и $im(T_{q,n})$ – количеств паросочетаний и независимых паросочетаний в $T_{q,n}$ – полном $q$-арном дереве высоты $n$. Показывается, что для любого $q\geqslant 2$ существует такое $b_q>1$, что при $n\to+\infty$ справедлива асимптотика
$$ m(T_{q,n})\sim\biggl(\frac{1+\sqrt{1+4\cdot q}}2\,\biggr)^{-1/(q-1)}\cdot(b_q)^{q^n}. $$
Показывается также, что для любого $q\in \{1,2,3\}$ существуют числа $a'_q$ и $b'_q>1$ такие, что $im(T_{q,n})\sim a'_q\cdot (b'_q)^{q^{n}}$ при $n\to+\infty$, а также для любого достаточно большого $q$ существуют числа $a^{1}_q\ne a^{2}_q$ и $b'_q>1$ такие, что при $n\to+\infty$ справедливы асимптотики
\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*}

Библиография: 7 названий.