CALCULATION OF THE NUMBER OF SOLUTIONS TO THE EQUATION OF THE FIRST MULTIPLICITY OF TYPES UNDER RESTRICTIONS ON THE FREQUENCY OF OCCURRENCE OF ALPHABET CHARACTERS

Abstract

The article considers the number of solutions to the equation of the first multiplicity of types,
composed of vectors of multiplicity of types, each element of which is the number of occurrences of
elements of a certain type (any sign of the alphabet) in the sample under consideration. The equation
of the first multiplicity of types relates the number of occurrences of elements of all types in
the sample under consideration and the volume of this sample. The main attention is paid to the
conclusion and proof of the correctness of the expression that determines the number of nonnegative
integer solutions of the equation of the first multiplicity of types under conditions of restrictions
on the frequency of occurrence of alphabet characters. The solution of the equation ofthe first multiplicity of types is the basis for calculating exact approximations of the probabilities
of statistical values by the first multiplicity method, where the exact approximations are Δexact
distributions that differ from the exact distributions by no more than a predetermined, arbitrarily
small value Δ. The value that expresses the number of solutions to the equation of the first multiplicity
of types is one of the values that determine the algorithmic complexity of the method of the
first multiplicity, without knowing the value of which it is impossible to determine the parameters
of samples for which, under restrictions on the computational resource, exact approximations of
distributions can be calculated. Also, the value expressing the number of solutions to the equation
of the first multiplicity of types is used in the method of the first multiplicity to limit the search area
for solutions to the equation. The number of solutions to the equation of the first multiplicity is
considered under conditions of restriction on the maximum value of the elements of the multiplicity
vector, and the case is considered when one or more elements of the alphabet may be missing in
the sample. First obtained the expression that defines the number of nonnegative integer solutions
to equations of the first multiplicity of types in terms of restrictions on the values of the frequencies
of occurrence of signs and the possibility of absence of one or more characters of the alphabet in
the sample reviewed. Analytical expressions are obtained that allow calculating the number of
integer nonnegative solutions of the equation of the first multiplicity of types for any values of the
alphabet power, the sample size, and the limit on the maximum frequency of occurrence of alphabet
characters. The form of the obtained expression allows you to use it when studying the algorithmic
complexity of calculating exact approximations of probability distributions of statistical
values with a pre-specified accuracy Δ.