Derive a formula for the number of partitions of n into parts that are odd and bigger than 1; e.g. a(12)=5 cases: 3+3+3+3, 5+7, 7+5, 3+9, 9+3.

Verify your formula by evaluating a(14).

P is for Padovan

I found the first 20 terms by hand:
0,0,1,0,1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49
which doesn't looks like much until you look at the differences between successive terms:
0,1,-1,1,0,0,1,0,1,1,1,2,2,3,4,5,7,9,12
This set of differences is just an offset of the original sequence by 5 so it appears the sequence is similar to the Fibonacci except here
P(n) = P(n-1) + P(n-5)

I mapped out P(16) = P(15) + P(11) but could not see how the relationship holds.  Then I looked up the sequence in the OEIS:
http://oeis.org/A000931
Which gives the relation as the Padovan sequence
P(n) = P(n-2) + P(n-3)
upon inspection this appears to work.  I was also able to show why this sequence follows the relation.

P(14) = 9 the partitions are
7+7, 5+9, 9+5, 3+11, 11+3, 3+3+3+5, 3+3+5+3, 3+5+3+3, 5+3+3+3
To the last number in each partition add 2.  These beccome some partitions of 16

P(13) = 7 the partitions are 13, 3+3+7, 3+7+3, 7+3+3, 3+5+5, 5+3+5, 5+5+3
To each of these partitions append "+3"
These become the other partitions of 16.

It is easy to see they don't overlap and they don't leave any out.  And in general this will also be the case.

As for a closed formula: I looked it up too.  It's similar to the Fibonacci but a bit messier because unlike the golden ratio, the ratio for this sequence is the root of a cubic equation.  It's still pretty neat.

Posted by Jer on 2013-01-24 16:52:10