Combinatorial generation algorithms based on AND/OR tree structures for a class of algebraic generating functions

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.

discrete structure, combinatorial generation, algebraic generating function, functional equation, recurrence formula, AND/OR tree

1. S. Kemp, “Digital 2024: Global overview report.” 2024, Accessed: Nov. 01, 2025. [Online]. Available: https://datareportal.com/reports/digital-2024-global-overview-report.

2. D. E. Knuth, The art of computer programming. Volume 4A: Combinatorial algorithms, part 1. USA: Addison-Wesley, 2011.

3. D. E. Knuth, The art of computer programming. Volume 4B: Combinatorial algorithms, part 2. USA: Addison-Wesley, 2022.

4. D. L. Kreher and D. R. Stinson, Combinatorial algorithms: Generation, enumeration, and search. USA: CRC Press, 1999.

5. E. Seyedi-Tabari, H. Ahrabian, and A. Nowzari-Dalini, “A new algorithm for generation of different types of RNA,” International Journal of Computer Mathematics, vol. 87, no. 6, pp. 1197–1207, 2010, doi: 10.1080/00207160802140049.

6. M. E. Nebel, A. Scheid, and F. Weinberg, “Random generation of RNA secondary structures according to native distributions,” Algorithms for Molecular Biology, vol. 6, p. 24, 2011, doi: 10.1186/1748-7188-6-24.

7. E. Onokpasa, S. Wild, and P. W. H. Wong, “RNA secondary structures: from ab initio prediction to better compression, and back,” in Data Compression Conference, 2023, pp. 278–287, doi: 10.1109/DCC55655.2023.00036.

8. M. Bellare, T. Ristenpart, P. Rogaway, and T. Stegers, “Format-preserving encryption,” Lecture Notes in Computer Science: International Workshop on Selected Areas in Cryptography, vol. 5867, pp. 295–312, 2009, doi: 10.1007/978-3-642-05445-7_19.

9. D. Luchaup, T. Shrimpton, T. Ristenpart, and S. Jha, “Formatted encryption beyond regular languages,” in ACM SIGSAC Conference on Computer and Communications Security, 2014, pp. 1292–1303, doi: 10.1145/2660267.266035.

10. A. V. Goldberg and M. Sipser, “Compression and ranking,” SIAM Journal on Computing, vol. 20, no. 3, pp. 524–536, 1991, doi: 10.1137/0220034.

11. Y. V. Shablya, “Compression of information objects using combinatorial generation methods based on AND/OR trees,” Proceedings of TUSUR University, vol. 27, no. 4, pp. 74–79, 2024, doi: 10.21293/1818-0442-2024-27-4-74-79.

12. Y. V. Shablya, D. V. Kruchinin, and V. V. Kruchinin, “Method for developing combinatorial generation algorithms based on AND/OR trees and its application,” Mathematics, vol. 8, no. 6, p. 962, 2020, doi: 10.3390/math8060962.

13. Y. V. Shablya, “A method for constructing combinatorial generation algorithms for context-free languages based on AND/OR tree structures,” Information Technologies, vol. 31, no. 9, pp. 465–476, 2025, doi: 10.17587/it.31.465-476.

14. Y. V. Shablya and D. V. Kruchinin, “Algorithms for ranking and unranking the combinatorial set of RNA secondary structures,” Discrete Mathematics, Algorithms and Applications, p. 2550059, 2025, doi: 10.1142/S1793830925500594.

15. P. Flajolet, P. Zimmerman, and B. Cutsem, “A calculus for the random generation of combinatorial structures,” Theoretical Computer Science, vol. 132, no. 1--2, pp. 1–35, 1994, doi: 10.1016/0304-3975(94)90226-7.

16. C. Martinez and X. Molinero, “A generic approach for the unranking of labeled combinatorial classes,” Random Structures and Algorithms, vol. 19, no. 3--4, pp. 472–497, 2001, doi: 10.1002/rsa.10025.

17. C. Martinez and X. Molinero, “Efficient iteration in admissible combinatorial classes,” Theoretical Computer Science, vol. 346, no. 2--3, pp. 388–417, 2005, doi: 10.1016/j.tcs.2005.08.028.

18. R. P. Stanley, Enumerative combinatorics. Volume 2. USA: Cambridge University Press, 1999.

19. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms. USA: Addison-Wesley, 1974.

20. “The On-Line Encyclopedia of Integer Sequences.” 2025, Accessed: Nov. 01, 2025. [Online]. Available: http://www.oeis.org/.

21. D. V. Kruchinin, V. V. Kruchinin, and Y. V. Shablya, “On some properties of generalized Narayana numbers,” Quaestiones Mathematicae, vol. 45, no. 12, pp. 1949–1963, 2022, doi: 10.2989/16073606.2021.1980448.