Amount of Compositions of a Number n into k parts when the components are limited to the range [1;m] with m<n

48 Views Asked by At

The number of compositions of a number n into k parts is given by the binomial coefficent ${n-1 \choose k-1}$.

Is there a closed formula to this question, when the summands of the composition are limited to a range [1;m] where m is an arbitrary number strictly smaller than n?

Example: Compositions of n=6 into k=3 parts with m = 3

(2,2,2),(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)

gives us 7 different compositions. The unrestricted composition has size

${5 \choose 2} = 10$

I tried this out for multiple combinations of numbers and I could not figure out a rule or a pattern that held for every combination of n,k and m.