Question

Find p(11) , p(12) where p(n) denotes the number of partitions of n.

Answer 1

The answer is the sum of   1, 1, 2, 3, 5, 7, 10, 11, 10,  5, 1  =  56.

Partitions are :
  11
  10 + 1
   9 + 1 + 1      or  9 + 2
   8 + 1 + 1 + 1    or  8 + 1 + 2   or 8 + 3
   7 + 1 + 1 + 1 + 1  or  7 + 2 + 1 + 1  or  7 + 2 + 2  or  7 + 3 + 1  or  7 + 4

   6+1+1+1+1+1, 6+2+1+1+1, 6+2+2+1, 6+3+2, 6+3+1+1,6+4+1, 6+5

   5+1+1+1+1+1+1,  5+2+1+1+1+1, 5+2+2+1+1, 5+2+2+2, 5+3+1+1+1,
         5+3+2+1, 5 +3+3, 5+4+1+1, 5+4+2, 5+5+1

   4+1+1+1+1+1+1+1, 4+2+1+1+1+1+1, 4+2+2+1+1+1, 4+2+2+2+1,
       4+3+1+1+1+1, 4+3+2+1+1, 4+3+2+2, 4+3+3+1, 4+4+1+1+1, 4+4+2+1,
       4+4+3,

   3+1+1+1+1+1+1+1+1, 3+2+1+1+1+1+1+1, 3+2+2+1+1+1+1, 3+2+2+2+1+1,
       3+2+2+2+2,  3+3+1+1+1+1+1, 3+3+2+1+1+1, 3+3+2+2+1,
       3+3+3+2, 3+3+3+1+1,

   2+2+2+2+2+1,2+2+2+2+1+1+1, 2+2+2+1+1+1+1+1, 2+2+1+1+1+1+1+1+1,
       2+1+1+1+1+1+1+1+1+1,

  1+1+1+1+1+1+1+1+1+1+1

so    p(11) = 56  by enumerating all possibilities.
==========================

By partition theorem:
     g(i) = (3 i² - i) / 2   = Euler's pentagonal number

  we calculate:   g(-4) = 26,   g(-3) = 15,  g(-2) = 7,  g(-1) = 2 ,  g(1) = 1,
                        g(2) = 5,  g(3) = 12,  g(4) = 22

$Partition(n) = \Sigma_i (-1)^{i+1} * Partition(n - g(i))$ 

  for all i  positive and negative except 0.


P(n) = … - P(n-26) + P(n-15)  - P(n-7) + P(n-2) + P(n-1) – P(n-5) + P(n-12) – P(n-22) + …
Partition(11) =  ...- Part(11-26) + Part(11-15) - Part(11-7) + Part(11 -2) + part(11-1) - Part(11-5) + part(11-12) - Part(11-22) + ....
Partition (11)  =  0+...+0 + 0 - Part(4) + Part(9) +Part(10) - Part(6) + 0 - 0 +...
         
p(11) = p(9) + p(10) - p(4) - p(6) = 56

  p(10) = p(9) + p(8) - p(3) - p(5) = 42
    p(9) = p(8) + p(7) - p(4) - p(2) = 30
       p(8) = p(7)+p(6)- p(3)- p(1) = 22
          p(7) = p(6)+p(5) - p(2) - p(0) =  15
             p(6) = p(5)+p(4) - p(1) = 11
                p(5) = p(4+p(3) - p(0) = 7
                   p(4) = p(3)+p(2) = 5     as P(4) = {1+1+1+1, 1+2+1, 2+1, 3+1 ,4}
                      p(3) = p(2)+p(1) = 3     as P(3) = { 1+1+1 , 1+2 , 3}
                         p(2) = p(1)+p(0)  = 2    as P(2) = set { 1+1, 2 }
                            p(1) = 1      as  P(1) = {1 } = P(0)
                                p(0) = 1    by definition
                                   p(i) = 0  for all i negative.


==================
p(12) = p(11) + p(10) - p(7) - p(5) + p(0)
        = 56 + 42 - 15 - 7 + 1 
       = 77