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 Δ.