1
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ Where Ive read about them I think the ordered ones have a special name "composition" instead of partition. $\endgroup$ – mathreadler Oct 2 '17 at 21:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Donald Splutterwit Oct 2 '17 at 22:09
  • $\begingroup$ @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). $\endgroup$ – emillime Oct 3 '17 at 8:48
  • $\begingroup$ 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. $\endgroup$ – Donald Splutterwit Oct 3 '17 at 19:14
  • $\begingroup$ @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. $\endgroup$ – emillime Oct 5 '17 at 15:30
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.