Эта публикация цитируется в
1 статье
Случайные свободные деревья и леса с ограничениями на кратности вершин
А. Н. Тимашёв
Аннотация:
Рассматриваются свободные (некорневые) деревья с
$n$ занумерованными вершинами, кратности которых принимают значения из некоторого фиксированного подмножества
$A$ множества целых неотрицательных чисел такого, что
$A$ содержит нуль,
$A\ne\{0\}$,
$A\ne\{0,1\}$ и наибольший общий делитель чисел
$\{k\mid k\in A\}$ равен единице. Получена асимптотика числа всех таких деревьев при
$n\to\infty$. В предположении, что на множестве этих деревьев задано равномерное распределение, для случайной величины
$\mu_r^{(A)}$ (
$r\in A$), равной числу вершин кратности
$r$ в случайно выбранном дереве, найдены асимптотики математического ожидания и дисперсии при
$n\to\infty$, а также доказаны локальная нормальная и пуассоновская теоремы для распределения вероятностей этой случайной величины. Для случая
$A=\{0,1\}$ получены оценки чисел всех лесов с
$n$ занумерованными вершинами, состоящих из
$N$ свободных деревьев, при
$n\to\infty$ и различных предположениях о функции
$N=N(n)$. Найдена асимптотика числа всех лесов из свободных деревьев с
$n$ вершинами, кратности которых не превосходят 1. Доказаны локальные нормальные и пуассоновские теоремы для числа деревьев заданного объема и общего числа деревьев в случайном лесе такого типа. Получены предельные теоремы, оценивающие распределение вероятностей случайной величины, равной объему дерева, содержащего вершину с фиксированным номером.
УДК:
519.2 Статья поступила: 10.07.2003
Переработанный вариант поступил: 24.09.2004
DOI:
10.4213/dm180