The listing and counting combinatorial algorithm for compositions of a natural number with constraints

O. V. Kuz'min^a, M. V. Strihar<sup>b

a</sup> Irkutsk State University
^b Zabaikalsky Institute of Railway Transport, Magistral'naya str.

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.

Keywords: composition of number, Pascal's hyperpyramid, Pascal's pyramid, Pascal's triangle, polynomial coefficients, trinomial coefficients, binomial coefficients, recurrence relation, generating function, Fibonacci numbers, Tribonacci numbers, Tetranacci numbers, Pentanacci numbers

UDC: 519.1, 519.116, 511.344

MSC: 05А05, 11B75, 11B39, 11P81

DOI: 10.36535/2782-4438-2025-239-13-24

 English version: Journal of Mathematical Sciences (New York), 2025, 292:3, 343–354