z-logo
open-access-imgOpen Access
Асимптотические свойства числа инверсий в раскрашенных деревьях
Author(s) -
Vladimir Vatutin
Publication year - 2019
Publication title -
математические вопросы криптографии
Language(s) - Russian
Resource type - Journals
eISSN - 2222-3193
pISSN - 2220-2617
DOI - 10.4213/mvk305
Subject(s) - physics
Рассматривается $b$-арное плоское корневое дерево $T,$ вершинамкоторого независимо и равновероятно присвоены цвета, обозначаемыебуквами алфавита $\mathcal{A}=\{ A_{1}<A_{2}<...<A_{m}\} .$Вершина $u\in T$ является предком вершины $v\in T$ ($u\precv)$, если путь, ведущий по ребрам от корня дерева к вершине $v,$проходит через вершину $u$. Обозначим $col(u)$ цвет вершины $u.$Раскраска пары $u\prec v$ образует инверсию,если $col(u)>col(v).$ Исследуются вероятностныехарактеристики общего числа инверсий в раскрашенном $b$-арном плоскомкорневом дереве фиксированной высоты и распределения случайных величин,являющихся функционалами от числа инверсий в поддеревьях такого дерева.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom