All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers > Sequences
Greetings from P (Posted on 2013-01-24) Difficulty: 2 of 5
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).

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution P is for what? | Comment 3 of 5 |
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information