The La Plata Mountains as seen from above the author’s
            home.


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.)

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)