z-logo
open-access-imgOpen Access
Асимптотические свойства числа инверсий в раскрашенных деревьях
Author(s) -
Vladimir Vatutin,
Vladimir Vatutin
Publication year - 2019
Publication title -
matematičeskie voprosy kriptografii
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