2
$\begingroup$

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]

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – paw88789 Dec 15 '18 at 18:04
  • $\begingroup$ What kind of constrain? Are you interested in the order of numbers to be summed? $\endgroup$ – Robert Z Dec 15 '18 at 18:06
  • $\begingroup$ @paw88789 Yes, in my case order is important, so 1 2 3 and 3 1 2 are different partitions of 6. $\endgroup$ – ИванКарамазов Dec 15 '18 at 18:20
  • 1
    $\begingroup$ Suggestion: Try writing a recurrence equation for this problem. $\endgroup$ – paw88789 Dec 15 '18 at 18:23
  • $\begingroup$ @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$ $\endgroup$ – ИванКарамазов Dec 15 '18 at 19:28
2
$\begingroup$

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$

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

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.