# Ordered Integer Partition of fixed size

I'm trying to find how many ways there are to partition n into k partitions with max value s. I've found many solutions that does this for unordered partitions. They use recursion and the say that p(n, k) = p(n-1, k-1) + p(n-k, k). But I can't get this to work with ordered partitions.

So I want to find a way to calculate p(n, k, s), preferably recursively. For example p(4, 3, 2) = 3. Because we can partition 4 into (2+1+1), (1+2+1), (1+1+2).

• Where Ive read about them I think the ordered ones have a special name "composition" instead of partition. – mathreadler Oct 2 '17 at 21:43
• Ordered partitions are also known (in combinatorial parlance) as compositions. It is also well known (& can be easily seen from the recurrence relation you state in your question) that they are enumerated by binomial coefficients. You require that the largest parts are $s$, ... this can be achieved by modifying the "boundary condtions" used to generate pascals triangle. – Donald Splutterwit Oct 2 '17 at 22:09
• @DonaldSplutterwit Thank you for pointing me in the right direction. That's why I didn't find much about it. I'm not entirely sure how to implement the boundaries in pascals triangle. When I've generated that before I've just used p(n) = p(n-1, k-1) + p(n-1, k). – emillime Oct 3 '17 at 8:48
• I did begin to compose an answer to your question. but I realised that the recurrence relation also needs to be modified & this problem is more difficult than I had first thought. Good luck in your quest for a closed form solution. – Donald Splutterwit Oct 3 '17 at 19:14
• @DonaldSplutterwit I managed to solve it with your help and some thinking. You can look through my answer and see if you find anything wrong. – emillime Oct 5 '17 at 15:30

As pointed out in the comments an ordered integer partition is actually called integer composition. I did some more searching with that term and didn't find the exact answer to my specific question, but I could come up with a solution myself.

As I wanted to solve it recursively I did some experimenting and realized the recursive relation, I'll explain it with an example. Let's say we want to find the number of compositions with length $4$ that sums up to $5$ and where no part is bigger than $3$, we call this $p(5, 4, 3)$.

Then we realize that we can't pick $3$ in the first part because by doing that we will get at least the sum $6$ if we pick $1$ in all other parts.

So what happens if we pick $2$ instead? Then we have $3$ parts left that needs to have the sum $5-2 = 3$. But we could also pick a $1$ in the first part. Then we have the sum $4$ left to be made with $3$ parts.

So now we know that $p(5, 4, 3) = p(3, 3, 3) + p(4, 3, 3)$

Now maybe you can see the pattern for the recursive relation?

$$p(n, k, s) = \sum_{i=1}^{s}{p(n-i, k-1, s)}$$

We just define everything that is not possible to $0$ and then we have the base case when $n$ and $k$ is $0$ that is equal to 1 (we use the empty part to get $0$).

Side note: I'm a more of a programmer than mathematician so please correct me if I wrote something wrong.