Subjects covered
What is a partition and how many ways can up to 50 objects
be partitioned?
An algorithm showing how to calculate this list
An algorithm showing how to calculate all possible
partitions for any given “N”
(Math notation is generally the same as that used in
Microsoft’s Excel. The MathNotation link
will also give examples of the notation as used here.)
What is a partition?
A partition is any of the possible ways of splitting a
group of “N” objects into subgroups. For example, there are
two different partitions for the number 2. You could split 2 into two
groups of one each, or you could keep both objects in the original
group of 2.
Number Number of
Listing of
in Group
Partitions Partitions
------------------------------------
1
1 1
2
2 2, 1-1
3
3 3, 2-1, 1-1-1
4
5 4, 3-1, 2-2, 2-1-1, 1-1-1-1
5
7 5, 4-1, 3-2, 3-1-1, 2-2-1,
2-1-1-1, 1-1-1-1-1
6
11 See algorithm (below) for
generating all
7
15 possible partitions given
“N”
8 22
9 30
10 42
11 56
12 77
13 101
14 135
15 176
16 231
17 297
18 385
19 490
20 627
21 792
22 1,002
23 1,255
24 1,575
25 1,958
26 2,436
27 3,010
28 3,718
29 4,565
30 5,604
31 6,842
32 8,349
33 10,143
34 12,310
35 14,883
36 17,977
37 21,637
38 26,015
39 31,185
40 37,338
41 44,583
42 53,174
43 63,261
44 75,175
45 89,134
46 105,558
47 124,754
48 147,273
49 173,525
50 204,226
For very large “N” use:
Total = EXP[PI()*SQRT(2*N/3) - LN(4*N*SQRT(3))]
An algorithm for generating the number of partitions for any
group size “N”
In the above list, if we look at the 5 possible partitions
for a group size of “4”, we note that we can create these
by the following rules. First, add another group containing
“1” member to all the partitions in the “Size
3” listing. Then add another group containing 2 members to all
partitions of the “Size 2” listing that have a smallest
member of 2 or greater. Using this rule we can construct the following table.
(Col 0) <----- Col. --->
N
Total 1 2
3 4 5
6 7 8
9 10
-------------------------------------------------------------
1 1 1
2 2
1 1
3 3
2 0 1
4 5
3 1 0 1
5 7
5 1 0
0 1
6 11
7 2 1
0 0 1
7 15 11
2 1 0
0 0 1
8 22 15
4 1 1
0 0 0 1
9 30 22
4 2 1
0 0 0
0 1
10 42 30
7 2 1
1 0 0
0 0 1
First, lets give a translation of what we are looking at:
(Also see listings at the top of the page)
For the “N” = 4 row:
If we are looking at all possible ways a group of 4 objects can be
partitioned, there are 5 possible ways this can be done. Under Col. 1,
there are three possible partitions that have a smallest member of
“1”, (3-1, 2-1-1, 1-1-1-1). Under Col. 2, there is
only one partition that has a smallest member of “2”,
(2-2). There are no ways the smallest member can be “3”.
There is only one way the smallest member can be “4” (e.g.
a simple 4). The total that appears in “Col 0” is the sum
of everything to the right of Col 0.
For the “N” = 5 row: (Group size = 5)
There are 5 possible partitions with a smallest member of
“1”
There is 1 possible partition with a smallest member of “2”
There is 1 possible partition with a smallest member of “5”
The total of 7 appears in Col. 0.
We can use rows 1-5 of the table to construct row 6.
The entry for row 6, col. 1 is the number of partitions that can be
generated by adding another group containing just 1 member to all
possible partitions for group 5. If we go up 1 row and take the sum of
all entries starting here and continuing to the right we get: 5 + 1 + 0
+ 0 + 1 = 7. Thus we place a 7 at row 6 col. 1.
The entry for row 6 col. 2 is the number of partitions that can be
generated by adding another group containing exactly 2 members to all
possible partitions for group 4 that have a smallest member of 2 or
greater. If we go up 2 rows in the table and take the sum of all
entries here and going to the right we get: 1 + 0 + 1 = 2. Thus we
place a 2 at row 6 col. 2.
The entry for row 6 col. 3 goes up 3 rows and only uses the
“1” (all other entries are blank).
Finally all other column entries are zero until we get to Col. 6 for
Row 6 (The general rule is col. “N” for row
“N”). Here we place another “1”.
The total for row 6 is the sum of all the cols. starting at col. 1.
We can construct row 7 using similar rules.
Row 7 Col. 1 = 7 + 2 + 1 + 0 + 0 + 1 = 11 (up 1 row)
Row 7 Col. 2 = 1 + 0 + 0 + 1 = 2 (up 2 rows)
Row 7 Col. 3 = 0 + 1 = 1 (up 3 rows)
Row 7 Cols. 4 to 6 = All zero
Row 7 Col. 7 = 1 (For any row “N” set Col. “N”
to 1)
Row 7 Col. 0 (Total) = 11 + 2 + 1 + 0 + 0 + 0 + 1= 15
The reader may want to calculate row 8 just to see how the algorithm
works. An algorithm that can solve a problem for any order
“N+1” given that a solution for order “N” is
known is called a recursive algorithm. Recursive algorithms can be used
to solve many problems in Computer Science and Applied Mathematics.
An algorithm for generating all possible partitions for any
given “N”
Probably the easiest way of understanding how to generate all possible
partitions for any given group size “N” is to give an
example. Here we will use “N” = 7.
The following table lists all partitions for group size = 7.
1,
1, 1, 1, 1, 1, 1 7 groups of 1 each
2, 1, 1, 1, 1,
1 One group of 2, five
1’s
2, 2, 1, 1,
1 Two
2’s, three 1’s
2, 2, 2,
1
Three 2’s, one 1
3, 1, 1, 1,
1 One
3, four 1’s
3, 2, 1,
1
One 3, one 2, two 1’s
3, 2,
2
One 3, two 2’s
3, 3,
1
Two 3’s, one 1
4, 1, 1,
1
One 4, three 1’s
4, 2,
1
One 4, one 2, one 1
4,
3
One 4, one 3
5, 1,
1
One 5, two 1’s
5,
2
One 5, one 2
6,
1
One 6, one 1
7
One 7
We can use a table to represent the same data:
Row Nbr. Nbr. Nbr. Nbr.
Nbr. Nbr. Nbr.
Number
1’s 2’s 3’s
4’s 5’s 6’s
7’s
-------------------------------------------------
1 7
2 5 1
3 3 2
4 1 3
5 4
0 1
6 2
1 1
7 0
2 1
8 1
0 2
9 3
0 0 1
10 1
1 0 1
11 0
0 1 1
12 2
0 0
0 1
13 0
1 0
0 1
14 1
0 0
0 0 1
15 0
0 0
0 0
0 1
We will give the rules for this order (N = 7), and then run through it
by hand to see how it works.
First initialize the system by placing 7 items in the “Nbr.
1’s” col. Then generate each of the subsequent rows until
you have finished processing the “1” in the “Nbr.
7’s” col.
Step 1) If you can subtract 2 from the number that appears in
“Nbr. 1’s”, then construct the next row as follows.
Subtract 2 from the “Nbr. 1’s” value. Add 1 to the
“Nbr. 2’s” value. Copy all the other columns. Repeat
Step 1).
Else if you can not subtract 2 from the “Nbr. 1’s”
value, use Step 2)
Step 2) Form the following calculation and cumulate the totals.
Initialize “Total” with whatever value was in the
“Nbr. 1’s” column. Set “Nbr. 1’s”
to 0
Multiply whatever is in the “Nbr. 2’s” col. by 2 and
add this amount to
“Total”
Set “Nbr. 2’s” to 0
Multiply whatever is in the “Nbr. 3’s” col. by 3 and
add this amount to “Total”
Set “Nbr. 3’s” to 0
Continue this process until “Total” is >=
“X” where “X” is the header number in the next
“Nbr. X’s” col.
Increment the value that was in the “Nbr. X’s”
column. Subtract “X” from “Total” and place the
result in the “Nbr. 1’s” column.
Copy all other columns to the right of the “X” column.
Go to Step 1).
Now let’s see how this works.
Row Nbr. Nbr. Nbr. Nbr.
Nbr. Nbr. Nbr.
Number
1’s 2’s 3’s
4’s 5’s 6’s
7’s
-------------------------------------------------
1 7
2 5 1
3 3 2
4 1 3
5 4
0 1
6 2
1 1
7 0
2 1
8 1
0 2
9 3
0 0 1
etc.
For row 1 we initialize the system with a “7”. Rows 2, 3,
and 4 only use Step 1). For row 5 we use Step 2).
First, set “Total” to whatever was left in the “Nbr.
1’s” col. and set “Nbr. 1’s” to zero.
“Total” equals 1.
“Total” is less than the col. header in the next col.
(“Nbr. 2’s”) thus we continue to the right.
Multiply whatever is in the “Nbr. 2’s” by 2 and add
the result to “Total”. “Total” is thus
increased by 3 * 2 and becomes 7. Set the “Nbr. 2’s”
column to 0.
The value of “Total” (7) is now >= than the
“3” header in “Nbr. 3’s”. Thus, increase
the 0 that was in the “Nbr. 3’s” column by 1. Then
subtract 3 from 7 yielding 4, which goes in the “Nbr.
1’s” col.
Rows 6 and 7 just use Step 1) again.
For row 8 we use Step 2).
The “Nbr. 1’s” column was 0. Thus “Total”
initially equals zero. Place a 0 in “Nbr. 1’s” col.
Multiply the 2 in “Nbr. 2’s” col. by 2 and add the
result to “Total”. “Total” now equals 4. Also
place a “0” in the “Nbr. 2’s” col.
“Total” is now >= than the header in the next col.
(“Nbr. 3’s”). Thus, increment the “Nbr.
3’s” col. from 1 to 2. Subtract 3 from the 4 in
“Total” and place the result (1) in the “Nbr
1’s” col.
Row 9 also uses Step 2)
Initialize “Total” with the “1” from
“Nbr. 1’s”. Set “Nbr. 1’s” to 0.
“Nbr 2’s” is 0, thus “Total” stays at 1.
Multiply the 2 in the “Nbr. 3’s” col. by 3 and add
the result to “Total”. “Total” is now equal to
7. (Set the “Nbr. 3’s” col. to 0).
“Total” is now >= than the 4 header in the next
“Nbr. X’s” col. Thus increment the 0 that was in
“Nbr. 4’s” by 1 to 1. Subtract the 4 from 7, and put
the result “3” back in the “Nbr. 1’s” col.
Return to Durango Bill's Home page
Web page generated via KompoZer