Durango Bill’s
Enumeration of Partitions
How many ways are there to separate “N” objects into different subgroups?
Subjects covered
What is a partition and how many ways can up to 100 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.)
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
51 239,943
52 281,589
53 329,931
54 386,155
55 451,276
56 526,823
57 614,154
58 715,220
59 831,820
60 966,467
61 1,121,505
62 1,300,156
63 1,505,499
64 1,741,630
65 2,012,558
66 2,323,520
67 2,679,689
68 3,087,735
69 3,554,345
70 4,087,968
71 4,697,205
72 5,392,783
73 6,185,689
74 7,089,500
75 8,118,264
76 9,289,091
77 10,619,863
78 12,132,164
79 13,848,650
80 15,796,476
81 18,004,327
82 20,506,255
83 23,338,469
84 26,543,660
85 30,167,357
86 34,262,962
87 38,887,673
88 44,108,109
89 49,995,925
90 56,634,173
91 64,112,359
92 72,533,807
93 82,010,177
94 92,669,720
95 104,651,419
96 118,114,304
97 133,230,930
98 150,198,136
99 169,229,875
100 190,569,292
200 3,972,999,029,388
300 9,253,082,936,723,602
400 6,727,090,051,741,041,926
500 2.3002E+21
1000 2.4061E+31
2000 4.7208E+45
3000 4.9603E+56
4000 1.0242E+66
5000 1.6982E+74
10000 3.6167E+106
The total for size = 10,000 cross checks with the list at https://qseries.org/fgarvan/data/ptncofs.txt
For very large “N” use:
Total = EXP[PI()*SQRT(2*N/3) - LN(4*N*SQRT(3))]
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.
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 Sea Monkey's Composer HTML editor
within a Linux Cinnamon Mint 18 operating system.
(Goodbye Microsoft)
What is a partition and how many ways can up to 100 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
51 239,943
52 281,589
53 329,931
54 386,155
55 451,276
56 526,823
57 614,154
58 715,220
59 831,820
60 966,467
61 1,121,505
62 1,300,156
63 1,505,499
64 1,741,630
65 2,012,558
66 2,323,520
67 2,679,689
68 3,087,735
69 3,554,345
70 4,087,968
71 4,697,205
72 5,392,783
73 6,185,689
74 7,089,500
75 8,118,264
76 9,289,091
77 10,619,863
78 12,132,164
79 13,848,650
80 15,796,476
81 18,004,327
82 20,506,255
83 23,338,469
84 26,543,660
85 30,167,357
86 34,262,962
87 38,887,673
88 44,108,109
89 49,995,925
90 56,634,173
91 64,112,359
92 72,533,807
93 82,010,177
94 92,669,720
95 104,651,419
96 118,114,304
97 133,230,930
98 150,198,136
99 169,229,875
100 190,569,292
200 3,972,999,029,388
300 9,253,082,936,723,602
400 6,727,090,051,741,041,926
500 2.3002E+21
1000 2.4061E+31
2000 4.7208E+45
3000 4.9603E+56
4000 1.0242E+66
5000 1.6982E+74
10000 3.6167E+106
The total for size = 10,000 cross checks with the list at https://qseries.org/fgarvan/data/ptncofs.txt
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 Sea Monkey's Composer HTML editor
within a Linux Cinnamon Mint 18 operating system.
(Goodbye Microsoft)