# Find Integer Partition using only integers belonging to S = { 1, 2, 3 }

I spent all afternoon looking for this but I wasn't able to find anything, so... Is there a formula to know the NUMBER of partitions with a constraint on the integer domain ?

E.g.: Find the number of partitions of 5 only using integers belonging to S = {1,2,3}

p(5) -> 13

Since p(5):

1. [1,1,1,1,1]

2. [1,1,1,2]

3. [1,1,2,1]

4. [1,2,1,1]

5. [2,1,1,1]

6. [2,2,1]

7. [2,1,2]

8. [1,2,2]

9. [1,1,3]

10. [1,3,1]

11. [3,1,1]

12. [3,2]

13. [2,3]

• Usually in giving a partition of an integer, order is not important. So one would not generally distinguish between 1, 2, 3 and 3, 1, 2 as partitions of $6$. Is your intent to consider 'ordered' partitions as you did in your example? – paw88789 Dec 15 '18 at 18:04
• What kind of constrain? Are you interested in the order of numbers to be summed? – Robert Z Dec 15 '18 at 18:06
• @paw88789 Yes, in my case order is important, so 1 2 3 and 3 1 2 are different partitions of 6. – ИванКарамазов Dec 15 '18 at 18:20
• Suggestion: Try writing a recurrence equation for this problem. – paw88789 Dec 15 '18 at 18:23
• @paw88789 Mmm thanks, I think I found the right solution. It seems a generalization of the FIbonacci sequence. $$P(n) = \sum_{i=1}^{k} P(n-i)$$ where $P(1) = 1$ , $P(2) = 2$ and $P(3) = 4$ – ИванКарамазов Dec 15 '18 at 19:28

Ok, the problem can be solved using a recurrence equation.

If we suppose $$n > m$$ the number of ordered partitions of $$n$$ will be: $$P_{k}(n) = \sum_{i=1}^{k} P_{k}(n-i)$$

Where $$P_{3}(1) = 1$$ , $$P_{3}(2) = 2$$ and $$P_{3}(3) = 4$$.

If we think about it the first number in our partition can be any number up to $$m$$.

So e.g. $$n = 5$$ and $$m = 3$$

• Start = 3

$$[3, 1, 1]$$ , $$[3, 2]$$

$$->$$ 2 partitions {$$P_{3}(5-3) = P_{3}(2)$$}

• Start = 2

$$[2, 1, 1, 1]$$ , $$[2, 2, 1]$$ , $$[2, 1, 2]$$ , $$[2, 3]$$

$$->$$ 4 partitions {$$P_{3}(5-2) = P_{3}(3)$$}

• Start = 1

$$[1, 1, 1, 1, 1]$$ , $$[1, 1, 1, 2]$$ , $$[1, 1, 2, 1]$$ , $$[1, 2, 1, 1]$$ , $$[1, 1, 3]$$ , $$[1, 3, 1]$$ , $$[1, 2, 2]$$

$$->$$ 7 partitions {$$P_{3}(5-1) = P_{3}(4)$$}

Finally:

$$P_{3}(5) = P_{3}(4) + P_{3}(3) + P_{3}(2) = 7 + 4 + 2 = 13$$

• It's arguably slightly easier to use base case $P_3(0) = 1$ instead of $P_3(4) = 4$. – Peter Taylor Dec 15 '18 at 22:58