РАСЧЕТ КОЛИЧЕСТВА РЕШЕНИЙ УРАВНЕНИЯ ПЕРВОЙ КРАТНОСТИ ТИПОВ В УСЛОВИЯХ ОГРАНИЧЕНИЙ НА ЧАСТОТУ ВСТРЕЧАЕМОСТИ ЗНАКОВ АЛФАВИТА

Аннотация

Рассматривается количество решений уравнения первой кратности типов, состав-
ленного из векторов кратности типов, каждый элемент которого представляет собой
число вхождений элементов определенного типа (какого-либо знака алфавита) в рассмат-
риваемую выборку. Уравнение первой кратности типов связывает между собой число
вхождений элементов всех типов в рассматриваемую выборку и объём этой выборки. Ос-
новное внимание в статье уделено выводу и доказательству правильности выражения,
определяющего количество неотрицательных целочисленных решений уравнения первой
кратности типов в условиях ограничений на частоту встречаемости знаков алфавита.
Решение уравнения первой кратности типов является основой расчета точных приближе-
ний вероятностей значений статистик методом первой кратности, где в качестве точ-
ных приближений выступают Δточные распределения, отличающиеся от точных рас-
пределений не более чем на заранее заданную, сколь угодно малую величину Δ. Величина,
выражающая количество решений уравнения первой кратности типов, является одной из
величин определяющих алгоритмическую сложность метода первой кратности, без знания
значения которой нельзя определить параметры выборок, для которых при ограничениях
на вычислительный ресурс могут быть рассчитаны точные приближения распределений.
Также величина выражающая количества решений уравнения первой кратности типов
используется в методе первой кратности для ограничения области поиска решений урав-
нения. Количество решений уравнения первой кратности рассматривается в условиях ог-
раничения на максимальное значение элементов вектора кратности, при этом рассматри-
вается случай, когда один или несколько элементов алфавита могут в выборке отсутст-
вовать. Впервые получено выражение, определяющее количество неотрицательных цело-
численных решений уравнения первой кратности типов в условиях ограничений сверху на
значения частот встречаемости знаков и возможности отсутствия одного или несколь-
ких знаков алфавита в рассматриваемой выборке. Получены аналитические выражения,
позволяющие для любых значений мощности алфавита, объёма выборки и ограничения на
значение максимальной частоты встречаемости знаков алфавита вычислять количество
целочисленных неотрицательных решений уравнения первой кратности типов. Вид полу-
ченного выражения позволяет использовать его при изучении алгоритмической сложности
расчетов точных приближений распределений вероятностей значений статистик с зара-
нее указанной точностью Δ.