В данной статье предложен систематический подход к разработке алгоритмов комбинаторной генерации для множеств дискретных структур, мощность которых задается коэффициентами алгебраических производящих функций и их степеней. Исследование базируется на наличии связи между операциями над производящими функциями и комбинаторными множествами. В качестве основы использован математический аппарат деревьев И/ИЛИ, который позволяет комбинировать алгоритмы комбинаторной генерации для простых подструктур в сложные комбинаторные объекты. При этом основным теоретическим результатом работы является вывод новых эффективных рекуррентных формул для вычисления значений коэффициентов алгебраических производящих функций и их степеней с полиномиальной вычислительной сложностью $O((n_1 + \ldots + n_m + m) \cdot n^2)$ по времени и $O(n^2)$ по памяти. На основе доказанных теорем о рекуррентных формулах, предложенный подход позволяет строить алгоритмы с полиномиальной оценкой вычислительной сложности, что делает их применимыми для решения практических задач в области прикладной дискретной математики и теоретической информатики. Кроме того, использование коэффициентов степеней производящих функций расширяет возможности генерации, так как это позволяет строить не только объекты исходного комбинаторного множества, связанного с производящей функцией, но и кортежи таких объектов. Апробация предложенного подхода показана на примерах получения рекуррентных формул и алгоритмов генерации на их основе для классических числовых последовательностей, таких как числа Фибоначчи, Пелля, Каталана, Моцкина и Шредера. Предложенный подход открывает новые возможности для решения задач оптимизации, моделирования и кодирования сложных дискретных структур, например, в таких областях как биоинформатика и криптография.
This paper proposes a systematic approach to developing combinatorial generation algorithms for sets of discrete structures whose cardinality is determined by the coefficients of algebraic generating functions and their powers. The study is based on the relationship between operations on generating functions and combinatorial sets. It uses the mathematical apparatus of AND/OR trees as a foundation, which allows combining combinatorial generation algorithms for simple substructures into complex combinatorial objects. The main theoretical result of the work is the derivation of new efficient recurrence formulas for calculating the values of the coefficients of algebraic generating functions and their powers with polynomial computational complexity $O((n_1 + \ldots + n_m + m) \cdot n^2)$ for time and $O(n^2)$ for memory. Based on proven theorems on recurrence formulas, the proposed approach enables the construction of algorithms with polynomial computational complexity estimates, making them applicable to solving practical problems in applied discrete mathematics and theoretical computer science. Moreover, the use of coefficients of generating function powers expands the generation capabilities, since it allows us to construct not only objects of the original combinatorial set associated with the generating function, but also tuples of such objects. Validation of the proposed approach is demonstrated using examples of deriving recurrence formulas and generation algorithms based on them for classical numerical sequences, such as the Fibonacci, Pell, Catalan, Motzkin, and Schroder numbers. The proposed approach opens up new possibilities for solving problems of optimization, modeling, and coding complex discrete structures, for example, in fields such as bioinformatics and cryptography.
The authors declare that there are no conflicts of interest present.