RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 1977, том 21, выпуск 1, страницы 65–70 (Mi mzm7930)

Асимптотические формулы для энумератора деревьев с заданным числом висячих или внутренних вершин

В. А. Воблый

Государственный научно-исследовательский и проектный институт лакокрасочной промышленности

Аннотация: Пусть $t(r,n)$ — число деревьев с $n$ вершинами, из которых $r$ — висячие, a $q$ — внутренние ($r=n-q$). Доказывается, что при фиксированном $r$ или $q$ справедливы асимптотические формулы ($r>2$)
\begin{gather*} t(r,n)\approx\frac1{r!(r-2)!}2^{2-r}n^{2r-4}\quad(n\to\infty), \\ t(n-q,n)\approx\frac1{q!(q-1)!}q^{q-2}n^{q-1}\quad(n\to\infty). \end{gather*}
При выводе этих формул не используется выражение для энумератора деревьев по числу висячих вершин. Библ. 7 назв.

УДК: 519.1

Поступило: 16.10.1975


 Англоязычная версия: Mathematical Notes, 1977, 21:1, 36–39

Реферативные базы данных:


© МИАН, 2024