|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Асимптотические свойства числа инверсий в раскрашенных деревьях
В. А. Ватутин Математический институт им. В.А. Стеклова Российской академии наук, Москва
Аннотация:
Рассматривается $b$-арное плоское корневое дерево $T,$ вершинам
которого независимо и равновероятно присвоены цвета, обозначаемые
буквами алфавита $\mathcal{A}=\left\{ A_{1}<A_{2}<...<A_{m}\right\} .$
Вершина $u\in T$ является предком вершины $v\in T$ ($u\prec
v)$, если путь, ведущий по ребрам от корня дерева к вершине $v,$
проходит через вершину $u$. Обозначим $\text{col}(u)$ цвет вершины $u.$
Раскраска пары $u\prec v$ образует инверсию,
если $\text{col}(u)>\text{col}(v).$ Исследуются вероятностные
характеристики общего числа инверсий в раскрашенном $b$-арном плоском
корневом дереве фиксированной высоты и распределения случайных величин,
являющихся функционалами от числа инверсий в поддеревьях такого дерева.
Ключевые слова:
$b$-арное корневое дерево, раскрашенное дерево, инверсия, предельные теоремы.
Получено 29.IV.2019
Образец цитирования:
В. А. Ватутин, “Асимптотические свойства числа инверсий в раскрашенных деревьях”, Матем. вопр. криптогр., 10:4 (2019), 9–24
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mvk305https://doi.org/10.4213/mvk305 https://www.mathnet.ru/rus/mvk/v10/i4/p9
|
Статистика просмотров: |
Страница аннотации: | 235 | PDF полного текста: | 141 | Список литературы: | 25 | Первая страница: | 4 |
|