Geodesic
The listing and counting combinatorial algorithm for compositions of a natural number with constraints
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the 6th International Conference "Dynamic Systems and Computer Science: Theory and Applications" (DYSC 2024). Irkutsk, September 16-20, 2024. Part 2, Tome 239 (2025), pp. 13-24.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: composition of number, recurrence relation, generating function, Fibonacci numbers, Tribonacci numbers, Tetranacci numbers, Pentanacci numbers
Mots-clés : Pascal's hyperpyramid, Pascal's pyramid, Pascal's triangle, polynomial coefficients, trinomial coefficients, binomial coefficients 
@article{INTO_2025_239_a1,
     author = {O. V. Kuz'min and M. V. Strihar},
     title = {The listing and counting combinatorial algorithm for compositions of a natural number with constraints},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {13--24},
     publisher = {mathdoc},
     volume = {239},
     year = {2025},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2025_239_a1/}
}
TY  - JOUR
AU  - O. V. Kuz'min
AU  - M. V. Strihar
TI  - The listing and counting combinatorial algorithm for compositions of a natural number with constraints
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2025
SP  - 13
EP  - 24
VL  - 239
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2025_239_a1/
LA  - ru
ID  - INTO_2025_239_a1
ER  - 
%0 Journal Article
%A O. V. Kuz'min
%A M. V. Strihar
%T The listing and counting combinatorial algorithm for compositions of a natural number with constraints
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2025
%P 13-24
%V 239
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2025_239_a1/
%G ru
%F INTO_2025_239_a1
O. V. Kuz'min; M. V. Strihar. The listing and counting combinatorial algorithm for compositions of a natural number with constraints. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the 6th International Conference "Dynamic Systems and Computer Science: Theory and Applications" (DYSC 2024). Irkutsk, September 16-20, 2024. Part 2, Tome 239 (2025), pp. 13-24. http://geodesic.mathdoc.fr/item/INTO_2025_239_a1/

[1] Borodin A. V., Biryukov E. S., “O prakticheskoi realizatsii nekotorykh algoritmov, svyazannykh s problemoi kompozitsii chisel”, Kibern. programm., 2015, no. 1, 27–45

[2] Kruchinin V. V., “Algoritmy generatsii i numeratsii kompozitsii i razbienii naturalnogo chisla $n$”, Dokl. TUSUR., 17:3 (2008), 113–119

[3] Kruchinin V. V., “Modifikatsiya metoda postroeniya algoritmov kombinatornoi generatsii na osnove primeneniya proizvodyaschikh funktsii mnogikh peremennykh i priblizhennykh vychislenii”, Dokl. TUSUR., 25:1 (2022), 55–60 | MR

[4] Kuzmin O. V., Obobschennye piramidy Paskalya i ikh prilozheniya, Nauka, Novosibirsk, 2000 | MR

[5] Kuzmin O. V., Strikhar M. V., “Kompozitsii chisel s ogranicheniyami i ierarkhicheskaya struktura ploskikh sechenii piramidy Paskalya”, Itogi nauki tekhn. Sovr. mat. prilozh. Temat. obz., 234 (2024), 67–74

[6] Kuzmin O. V., Seregina M. V., “Ploskie secheniya obobschennoi piramidy Paskalya i ikh interpretatsii”, Diskr. mat., 22:3 (2010), 83–93 | DOI | MR | Zbl

[7] Strikhar M. V., “Summa elementov secheniya giperpiramidy Paskalya giperploskostyu”, Aktualnye zadachi prikladnoi diskretnoi matematiki, ed. O. V. Kuzmin, Izd-vo IGU, Irkutsk, 2024

[8] Endryus G., Teoriya razbienii, Nauka, M., 1982

[9] Okbaeva N., “Pascal's triangle, its planar and spatial generalizations”, Int. Sci. J. Theor. Appl. Sci., 03 (107) (2022), 815–823

[10] Sloane N. J. A., The on-line encyclopedia of integer sequences, https://oeis.org | MR