The listing and counting combinatorial algorithm for compositions of a natural number with constraints
- Authors: Kuz'min O.V.1, Strihar M.V.2
-
Affiliations:
- Irkutsk State University
- Zabaikalsky Institute of Railway Transport
- Issue: Vol 239 (2025)
- Pages: 13-24
- Section: Articles
- URL: https://ogarev-online.ru/2782-4438/article/view/312523
- DOI: https://doi.org/10.36535/2782-4438-2025-239-13-24
- ID: 312523
Cite item
Full Text
Abstract
In this paper, we propose a listing and counting algorithm for compositions of a natural number based on combinatorial objects of a hierarchical structure, such as Pascal's triangle, Pascal's pyramid, and Pascal's hyperpyramids. We obtain the recurrent relation that is the basis for listing and counting of compositions of a natural number with an arbitrary constraints on the values of its natural parts and the formula for explicit counting of compositions and a generating function for the number of compositions.
About the authors
Oleg Viktorovich Kuz'min
Irkutsk State UniversityDoctor of physico-mathematical sciences, Professor
Marina Valerievna Strihar
Zabaikalsky Institute of Railway Transport
References
- Бородин А. В., Бирюков Е. С., “О практической реализации некоторых алгоритмов, связанных с проблемой композиции чисел”, Киберн. программ., 2015, № 1, 27–45
- Кручинин В. В., “Алгоритмы генерации и нумерации композиций и разбиений натурального числа ”, Докл. ТУСУР., 17:3 (2008), 113–119
- Кручинин В. В., “Модификация метода построения алгоритмов комбинаторной генерации на основе применения производящих функций многих переменных и приближенных вычислений”, Докл. ТУСУР., 25:1 (2022), 55–60
- Кузьмин О. В., Обобщенные пирамиды Паскаля и их приложения, Наука, Новосибирск, 2000
- Кузьмин О. В., Стрихарь М. В., “Композиции чисел с ограничениями и иерархическая структура плоских сечений пирамиды Паскаля”, Итоги науки техн. Совр. мат. прилож. Темат. обз., 234 (2024), 67–74
- Кузьмин О. В., Серегина М. В., “Плоские сечения обобщенной пирамиды Паскаля и их интерпретации”, Дискр. мат., 22:3 (2010), 83–93
- Стрихарь М. В., “Сумма элементов сечения гиперпирамиды Паскаля гиперплоскостью”, Актуальные задачи прикладной дискретной математики, ред. О. В. Кузьмин, Изд-во ИГУ, Иркутск, 2024
- Эндрюс Г., Теория разбиений, Наука, М., 1982
- Okbaeva N., “Pascal's triangle, its planar and spatial generalizations”, Int. Sci. J. Theor. Appl. Sci., 03 (107) (2022), 815–823
- Sloane N. J. A., The on-line encyclopedia of integer sequences, https://oeis.org
Supplementary files
