Count selections with the composition function

composition(n, k) counts the ways to write a non-negative integer n as a sum of k non-negative parts. Order matters: splitting 5 as 2 + 3 differs from 3 + 2. This is the familiar “stars and bars” counting problem and is valuable for distributions, allocations, and coefficient calculations.

What the result represents

For example, composition(5, 3) counts distributions of five identical items among three labelled boxes, allowing empty boxes. A result can be checked with the binomial expression combinations(n + k - 1, k - 1). The related combinations function counts choices where order does not matter, while permutations counts ordered arrangements of distinct objects.

Examples and modelling choices

If three teams receive a total of ten identical tokens, use composition(10, 3). If every team must receive at least one token, allocate one token to each team first, then calculate composition(7, 3). Be explicit about whether parts may be zero; that assumption changes the problem. For a multinomial allocation of distinguishable items, use multinomial instead.

Domain caveats

n and k should be non-negative integers, and k should describe a meaningful number of parts. Counts grow rapidly, so exact integer output can become very large. Use factorial only for the corresponding formula when you understand its larger intermediate values. For repeated distribution calculations, combinationsWithRep is also worth comparing.