Abstract:
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.
Fulltext:
PDF file (1666 kB)