View Single Post
jleach
jleach is offline
#9
Oct11-10, 09:53 AM
P: 17
I'm back and I've reviewed my notes. Restricted partitions is a little more complex than I described above, but not bad. The first thing that you'll need is a partition table like the one that I posted on Wikipedia (Search for "Integer Partitions" or "Partition (Number Theory)", then look under the section "See also". My table is the link called "Leibniz's distribution table for integer partitions". Leibniz is the one who beat me to the discovery. This table is actually two overlapping tables. One is for partitioning finite integers and the other is for partitioning infinity. You'll want to use the column for finite integers. From what I've read, everyone should already know the pattern to recreate this table. The stage values tell you how many ways you are going to divide the integer, but the stage values run opposite the number of divisions. For example, stage 1 will always be a set of all ones, but there will be N one's within that set.

As I said before, this is a fractal pattern that can only be described in terms of the repeating pattern within the table. Therefore, my solutions are in terms of the table coordinates. The next thing to remember is that the table coordinate (Column 0 Row 0) = 1.

Here's the solution:
Let N = The integer to be partitioned
Let S = The number of spaces or divisions of that number
Let E = Summation of i as i goes from 1 to S
Let L = Greatest integer function of (-1+sqrt(1+8*N))/2
The number of partition sequences without repeated values at S divisions is the coordinate (Column N-E+1, Row N-E+S).
Therefore, the total number of partitions sequences without repeated values is:
Summation of S from 1 to L of (Column N-E+1, Row N-E+S).

To check a practice run, let N=14. The answer should be 1 + 6 + 10 + 5 = 22