Matematicheskie Zametki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Matematicheskie Zametki, 2022, Volume 111, Issue 3, Pages 393–402
DOI: https://doi.org/10.4213/mzm13094
(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
References:
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.
Funding agency Grant number
Russian Science Foundation 21-11-00194
This work was supported by the Russian Science Foundation under grant no. 21-11-00194.
Received: 03.04.2021
English version:
Mathematical Notes, 2022, Volume 111, Issue 3, Pages 398–406
DOI: https://doi.org/10.1134/S0001434622030075
Bibliographic databases:
Document Type: Article
UDC: 519.17
Language: Russian
Citation: N. A. Kuz'min, D. S. Malyshev, “Enumeration of Matchings in Complete $q$-ary Trees”, Mat. Zametki, 111:3 (2022), 393–402; Math. Notes, 111:3 (2022), 398–406
Citation in format AMSBIB
\Bibitem{KuzMal22}
\by N.~A.~Kuz'min, D.~S.~Malyshev
\paper Enumeration of Matchings in Complete $q$-ary Trees
\jour Mat. Zametki
\yr 2022
\vol 111
\issue 3
\pages 393--402
\mathnet{http://mi.mathnet.ru/mzm13094}
\crossref{https://doi.org/10.4213/mzm13094}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4461269}
\transl
\jour Math. Notes
\yr 2022
\vol 111
\issue 3
\pages 398--406
\crossref{https://doi.org/10.1134/S0001434622030075}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85148591792}
Linking options:
  • https://www.mathnet.ru/eng/mzm13094
  • https://doi.org/10.4213/mzm13094
  • https://www.mathnet.ru/eng/mzm/v111/i3/p393
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математические заметки Mathematical Notes
    Statistics & downloads:
    Abstract page:179
    Full-text PDF :21
    References:32
    First page:5
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024