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

Question

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]

Answer 1

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$