Question

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

Answer 1

The partitions of 11 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+1+2, 5 +3+3, 5+4+1+1, 5+4+2, 5+5+1, 5+6
   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, 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

        p(11) = 56 or 57   by enumerating all possibilities.
==========================
By partition theorem:
     g(i) = (3 i² - i) / 2   = Euler's pentagonal number

$Partition(n) = \Sigma_i (-1)^{i+1} * Partition(n - g(i))$  for all i  positive and negative except 0.

     g(-4) = 25,   g(-3) = 15,  g(-2) = 7,  g(-1) = 2 ,  g(1) = 1,  g(2) = 5,  g(3) = 12,  g(4) = 22

Partition(11) =  ...- Part(11-25) + 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) = 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