Help with integer partitions
I'm still new to integer partition and I've gotten this far.
The number of order independant ways you can partition an integer into a set of numbers whose sum is N is defined as P(n).
Some examples are P(5)=7, P(8)=22 , and P(10)=42.
Let P(n,k) be the number of partitions in which each member is at least k. Also this is congruent to the number of partitions with at least k members.
$\displaystyle P(n,k) = 0\ if \ k>n$
$\displaystyle P(n,k) = 1\ if\ k=n$
$\displaystyle P(n,k) = P(n,k+1) + P(n-k,k)$
If I say P(10,5) that is the set of all partitions of 10 whose members are all >=5.
Which in this case (10,5)=2. 10 and 5+5.
Is there a way to find the partitions of X in which all the members <=K ? I've been trying to figure out some way to add and/or subtract various P(n,k) values to achieve this but i'm at a lost.
I did see some pages on the generating functions of P(n), but I haven't fully understood them yet. Am I going to be forced to use the generating function to get what I want? Namely the number of Partitions of X whose members are all <= to some K
Re: Help with integer partitions
Do you know the 'little book' MATHEMATICS OF CHOICE by Ivan Niven?
There is a very nice discussion of this topic in that book.
I have programmed MathCad to produce a table of partitioning an integer N into k or fewer summands. The recursion used is similar to the one you posted.