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

Матем. вопр. криптогр., 2019, том 10, выпуск 4, страницы 9–24 (Mi mvk305)

Эта публикация цитируется в 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$-арное корневое дерево, раскрашенное дерево, инверсия, предельные теоремы.

УДК: 519.212.2+519.214

Получено 29.IV.2019

DOI: 10.4213/mvk305



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


© МИАН, 2024