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

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)