Combinations

Basic Information

If some of the math symbols, terms and concepts are not familiar, then you may find an explanation at Math Definitions.

Introduction

When I was introduced to combinations, I did not fully comprehend the formula for combinations.  In the basic formula of m! divided by the product of (m-n)! and n!, the divisors remove the extra versions added by the permutation formula, m!. Removing the extra permutations is reasonable, but why does the end result equal the number of combinations taken n at a time? The development of a construction method that ties to the formula might provide an answer and it might also provide another way to calculate combinations, or it might help to explain why the formula works. But first, what is a combination?

Unlike permutations, combinations are a group of values in no particular order.  So, two permutations, (a,b,c) and (b,a,c) represent the same combination [a,b,c] or [c,b,a].  If the combination sets each have the same members, then they are the same combination, while 2 permutations containing the same elements displayed in a different order are two different permutations.

Mathematical Induction

The mathematics of combinations relies a great deal on mathematical induction, so a short description is in order.

Mathematical induction is a method of proving a theorem where a mathematical formula or equation applies to a series of cases, and the objective is to prove that the formula or equation applies to each case, even if there are an infinite number of cases. The series should be constructed in a specific order so that the first case can be defined, and, given that case(n) exists, there is case(n+1).

The method of proof starts with the first step of proving that the formula applies to case(1). The second step assumes that the formula applies to case(n) and proves that it also applies to case(n+1). The combination of these two steps proves that the formula applies to every case. The first step proves that the first case is true. The second step proves that, given case(n) is true, then case(n+1) is true. Since case(1) is true, then the second step implies that case(2) is true, and also that case(3) is true. Continuous applications of the second step implies that all cases are true.

In the example, we will develop a proof for the sum of the integers from 1 to n.

Case(1) shows that the formula applies to the sum of the integer 1.

i = n + 1 i = n n ⋅ (n + 1) n ⋅ (n + 1) 2 ⋅ (n + 1) n ⋅ (n + 1) + 2 ⋅ (n + 1) Σ i = Σ i + (n + 1) = ————— + (n + 1) = ————— + ————— = ——————————             i = 1 i = 1 2 2 2 2   i = n + 1 (n + 2) ⋅ (n + 1) (n + 1) ⋅ (n + 2) Σ i = ———————— = ————————                                                             i = 1 2 2

Case(n) shows that if the formula applies to the sum of 1 to n, then it applies to the sum of 1 to n+1. given that the formula applies sum of the number 1, then successive applications of the proof for case(n) shows that the formula applies to all sums of integers from 1 to n.

Defining Permutations and Combinations

Given the set {a,b,c} that contains 3 members, the set of permutations taken 2 members at a time are:

P({a,b,c},2) = {(a,b), (b,a), (c,a), (a,c), (c,b), (b,c)}

Combinations use a base set Α = {a,b,c} to derive the combinations. The combinations are defined in the set C(m,n), where m is the cardinality of Α and n is the width of each combination. The set of combinations for the set Α are:

Α = {a,b,c}, |Α| = 3
C(3,2) = {[a,b], [c,a], [c,b]}
|C(3,2)| = 3

In the examples shown above there are 6 permutations and just 3 combinations, 2 permutations with the same elements in a different sequence are different permutations, but 2 combinations with the same elements in a different sequence are the same combinations.

Permutations (a,b) ≠ (b,a), but combinations [a,b] = [b,a]

Constructing Combinations

A simple example shows a constructed set of combinations.

A set of combinations, each with a length of n members requires a set with m members, where m ≥ n. For example:

Α = {1,2,3}
C(3,2) ={[1,2],[1,3],[2,3]}

One way to determine the number of combinations is to build the combinations and then use the building method to determine the counting formula, and a consistent building method can help. We will start by explaining how the set of combinations shown above is constructed.

The construction starts with a base set containing 0 or more distinct members. All combinations in the array described below contain only members extracted from the base set.

The combination sets are arrayed in rows and columns. Each column contains combinations starting with a width of 0 and increasing the width by 1 with each successive column. The column defines the n-value in the combination formula. The first row starts with 0 members from the base set. Each succeeding row adds 1 member from the base set. Once a member of the base set is added to a row, it cannot be chosen again. Each row contains 1 new member. The row rank starts with 0 and increases by 1 for each succeeding rank, so the row rank equals the number of members extracted from the base set up to that point. The extracted members up to that point define the base set used to build combination sets for that row.

The building process relies on the fact that the base file for the next row is the same file plus 1 new member, so the set for the current row can be built from the sets created in the previous row that contain the same elements minus the new member. Therefore, we should find the combinations that don’t contain the new member, and we should find a way to derive the combinations that contain the new member.

The method that works is a version of the permutation building method, except that the new set can contain combinations with the new member and combinations without the new member. Suppose we are building the set C(m,n). The set C(m-1,n) contains all the combinations not containing the new member. The set C(m-1,n-1) can be used to build all the combinations containing the new member by adding the new member to each combination in C(m-1,n-1). Because the two sets C(m-1,n-1) and C(m,n-1) are complete and distinct, the union of the created set and C(m,n-1) will contain all the combinations for C(m,n).

The build process for C(m-1,n-1) uses the new member from the base set added in row m. The process constructs a new set by appending the new member x to each member of C(m-1,n-1) to create Α(n), where the members of Α are combination s of width n.

Let x be the new member added to the row set, and let [1,2,3] ∈ C(m-1,n-1).
[1,2,3,x] = [1,2,3] append x
[1,2,3,x] ∈ Α
Thus, Α = C(m-1,n-1) append x

The building process starts with the first row containing no members. Each succeeding row adds 1 new member from the base file and generates combinations using all of the members that have been added to the process for all columns with an n-value from 1 to the number of members added. The first member added generates combinations for column 1. The second member added generates combination s for column 1 and column 2. And the process continues naturally in the same way. Building combinations from the base set ensures that combination sets with a lower m-value and the same n-value are subsets of the higher m-value combination set.

There are three exceptions, one for C(0,0), one for the n=0 row and one for each entry where m=n. With the C(0,0) exception, there is no previous entry, so the set must simply be defined. With the n=0 exception, there is no n-1 column, so each subsequent row only uses the previous entry in the n=0 column. With the m=n exception, there is no entry for C(m,n-1), so each subsequent entry builds on C(m-1,n-1).

In the case of C(0,0) when m = n = 0 when the set of combinations generated from the null set that has no members, the combination of 0-length has no members. This empty combination is the only member of the set C(0,0).

The general case when m > n > 0:
Let x be the new member introduced on row m
C(m,n) C(m-1,n) = ∪ C(m-1,n-1) append x

The case when m = n = 0:
C(0,0) = {[ ]} and |C(0,0)| = 1

The case when m > 0 and n = 0:
C(m,0) = C(m-1,0) and |C(m,0)| = |C(m-1,0)| = 1

The case when m = n > 0:
Let x be the new member introduced on row m
C(m,m) = C(m-1,m-1) append x and |C(m,m)| = |C(m-1,m-1)|

The building process can be mapped in a table of combinations. The empty Combination table looks like this:

We now need to fill in the columns starting with n=0.

Null Combinations

The methodology for building a Null combination varies from the general model, because there is no column labeled 0-1. So, the construction comes from the elements with m-values less than the current value.

The first step is to define the combination set for m=n=0. There are no members to be combined, so the combination set is simply the 1-member set with a 0=length combination. Then apply the exception for n=0 combinations, C(m,0) = C(m-1,0) to show by induction that each combination in the n=0 row has the combination set {[ ]}. Specifically:

C(0,0) = {[ ]}.

The exception rule for n=0: C(x,0) = C(x-1,0)
By induction, C(m,0) = {[ ]}, for all m.

The application of the exception rule for n=0 implies that the set of combinations for row m equals the set of combinations from row m-1. Therefore, by induction, the set of combinations is the same for all m.

The next step is to define the other combinations in the n=0 row. We know what C(0,0) contains. can apply the rule for the n=0 row and show by induction what the other values will be.

The combination matrix with n=0 constructed:

Combinations with m = n > 0

Combinations with row-m = column-n, where n > 0 are combinations in which the cardinality of the base set equals the width of the combination. In this case, every member of the base set is in the combination. There is no combination C(m,x), where x < n, so the combination C(m,m) is built from the combination C(m-1,m-1), the starting combination from the previous row. In this case:

The case when m = n > 0:
Let x be the new member introduced on row m
C(m,m) = C(m-1,m-1) append x

The first three examples will show the pattern. To verify the values, refer to the previous combination matrix.

The case when m = n = 1:
The new member is 1
C(1,1) = C(0,0) append 1 = {[ ]} append 1 = {[1]}

The case when m = n = 2:
The new member is 2
C(2,2) = C(1,1) append 2 = {[1]} append 2 = {[1,2]}

The case when m = n = 3:
The new member is 3
C(3,3) = C(2,2) append 3 = {[1,2]} append 3 = {[1,2,3]}

The Combination Matrix becomes:

General Case Combinations

Combinations with row-m > column-n and where n > 0 are combinations that are built using the general case formula in which the membership of the new set is the union of two sets from row m-1, namely the combinations with column value equal to n and n-1. The new set contains all the members from the preceding set with column equal to n and new members from column n-1 with the new element defined in row-m appended to each combination. The general formula is:

The general case when m > n > 0:
Let x be the new member introduced on row m
C(m,n) = C(m-1,n) ∪ C(m-1,n-1) append x

The building formula assumes that the two sets combined to make the new set are valid combination sets. Since the border sets are valid combination sets, including C(1,0) and C(1,1), then the first general set, C(2,1) can be built from C(1,0) and C(1,1). The other non-border sets can be constructed in an order that provides the two building sets needed to build the next set.

The general case introduces a new element to create C(m,n). C(m-1,n-1) contains all the n-1 combinations for the set elements minus the new member, so amending the new element will create all the n combinations using the new element. C(m-1,n) contains all the combinations of n elements that do not in clude the new element. So the union of the two sets will generate the complete set as long as the C(m-1,n-1) and C(m-1,n) are complete.

Completeness can be shown with induction. Clearly the border sets are complete, so C(1,0) and C(1,1) are complete. As long as we build new sets from border sets and completed sets, then all sets will be complete, by induction. From C(1,0) and C(1,1) we can build C(2,1). The third-row combinations can be built grom the second-row combinations, and each succeeding row can be built as well with all combination sets being complete.

Examples of the general case are shown below. Pay attention to the order in which the sets are built. Review the previous matrix for the representations of the starting combination sets.

The general case for C(2,1), C(3,1), and C(3,2):
The new member is 2
C(2,1) = C(1,1) ∪ C(1,0) append 2 = {[1]} ∪ {[ ]} append 2 = {[1]} ∪ {[2]} = {[1],[2]}
The new member is 3
C(3,1) = C(2,1) ∪ C(2,0) append 3 = {[1],[2]} ∪ {[ ]} append 3 = {[1],[2]} ∪ {[3]} = {[1],[2],[3]}
C(3,2) = C(2,2) ∪ C(2,1) append 3 = {[1,2]} ∪ {[1],[2]} append 3 = {[1,2]} ∪ {[1,3],[2,3]} = {[1,2],[1,3],[2,3]}

The general case for C(4,1), C(4,2), and C(4,3):
The new member is 4
C(4,1) = C(3,1) ∪ C(3,0) append 4 = {[1],[2],[3]} ∪ {[ ]} append 4 = {[1],[2],[3]} ∪ {[4]} = {[1],[2],[3],[4]}
C(4,2) = C(3,2) ∪ C(3,1) append 4 = {[1,2],[1,3],[2,3]} ∪ {[1,4],[2,4],[3,4]} = {[1,2],[1,3],[2,3],[1,4],[2,4],[3,4]}
C(4,3) = C(3,3) ∪ C(3,2) append 4 = {[1,2,3]} ∪ {[1,2,4],[1,3,4],[2,3,4]} = {[1,2,3],[1,2,4],[1,3,4],[2,3,4]}

The Combination Matrix, with the next combinations filled in, becomes:

The 5^th row is left to the reader to construct. If you have success, then, by mathematical induction, the 6^th row will be easy as well.

Counting Combinations Formula

The formula for the number of combinations of m things taken n at a time is an extension of the permutation formula using factorials. For combinations, the permutation calculation for the set of m things is divided by the number of permutation calculation for the extracted set of n things and also divided by the permutation calculation for the complimentary set of m-n things. The divisions account for the variations in the sets of members taken away. While I could verify that the formula works, I never fully understood why it works. The formula is as follows:

                       m!
C(m,n) = —————
                (m-n)! ⋅ n!

Where |set of m things| = m and the length of each combination is n.

Counting Combinations

Combination sets can be counted simply by constructing the sets and then counting the members. And if you know the cardinality of the appropriate sets in the preceding row, then you can just add the membership counts of the two building sets to determine the cardinality and count of the target set. But using the formula for the cardinality of a given set is more direct and easier than working through a combination matrix. Although, a computer program could easily navigate a matrix starting at C(1,0) and C(1,1) to derive the desired cardinality by adding a chain of sets until the program reaches the desired set.

The following derivations will verify that the formula shown above applies to any combination set. The analysis will start with the exception sets along the boundaries and show that the general formula for the boundary sets always has the value of 1. The analysis will end by showing that any target combination formula can be derived from the formulas for the two combination sets that build the target. These three steps, when combines, prove inductively that the formula applies to any combination.

Counting Border Sets

The first border set contains combinations for n = 0. The following analysis determines the value of |C(m,0)| using the standard combination formula. The analysis will show that |C(m,0)| = 1, where m is the cardinality of the base set, and the combination has a n-value = 0 indicating an empty combination.

The second border set contains combinations where m = n > 0. The following analysis determines the value of |C(m,m)| using the standard combination formula. The analysis will show that |C(m,m)| = 1 for any nonnegative m, where m is the cardinality of the base set. Since the analysis applies to any nonnegative n, it also applies to n > 0.

The combination matrix showing the cardinality of each set is shown below for the border sets.

Counting in the General Case

Counting in the general case uses a variation of the build formula for the general case, which includes an append operation on C(m-1,n-1). The append operation simply changes each member of C(m-1,n-1) but doesn’t change the number of members, so:

|C(m,n)| = |C(m-1,n)| + |C(m-1, n-1) append x| = |C(m-1,n)| + |C(m-1, n-1)|

The building formula assumes that the two sets combined to create the new set are valid combination sets.

The following analysis shows that the standard cardinality formula supports the cardinality calculation shown above. The cardinality of a target set is the sum of the cardinality of the two sets that built the target set. Calculating cardinality should follow the same order as when building the sets. The calculations are shown below.

This analysis shows that the counting formula using factorials is correct. The advantage of the formula is the ability to calculate the cardinality without adding the cardinalities of many sets. The induction approach follows the same methodology for creating sets and counting sets. The purpose here is to show that the formula applies to all combination sets.

Calculating the cardinality of C(2,1), C(3,1), and C(3,2):
|C(2,1)| = |C(1,1)| + |C(1,0)| = 1 + 1 = 2
|C(3,1)| = |C(2,1)| + |C(2,0)| = 2 + 1 = 3
|C(3,2)| = |C(2,2)| + |C(2,1)| = 1 + 2 = 3

Calculating the cardinality of C(4,1), C(4,2), and C(4,3):
|C(4,1)| = |C(3,1)) + |C(3,0)| = 3 + 1 = 4
|C(4,2)| = |C(3,2)| + |C(3,1)| = 3 + 3 = 6
|C(4,3)| = |C(3,3)| + |C(3,2)| = 1 + 3 = 4

The combination matrix showing the cardinality of the non-border sets is shown below.

The 5^th row is left to the reader to construct. If you have success, then, by mathematical induction, the 6^th row will be easy as well.

Showing that the general formula for calculating the cardinality applies to the non-border sets uses mathematical induction. Since the cardinality of non-border sets relies on the two preceding sets or |C(m,n)| = |C(m-1,n-1)| + |C(m-1,n)|, then we need to show:

(m-1)! (m-1)! (m-1)! (m-1)! (m-1)! (m-1)! |C(m,n)| = ———————— + —————— = ———————— + —————— = —————— + ————— (m-1-(n-1))! ⋅ (n-1)! (m-1-n)! ⋅ n! (m-1-n+1)! ⋅ (n-1)! (m-n-1)! ⋅ n! (m-n)! ⋅ (n-1)! (m-n-1)! ⋅ n!

n ⋅ (m-1)! (m-n) ⋅ (m-1)! n ⋅ (m-1)! (m-n) ⋅ (m-1)! n ⋅ (m-1)! + (m-n) ⋅ (m-1)! = ———————— + ———————— = ————— + —————— = ——————————— n ⋅ (m-n)! ⋅ (n-1)! (m-n) ⋅ (m-n-1)! ⋅ n! (m-n)! ⋅ n! (m-n)! ⋅ n! (m-n)! ⋅ n!

n ⋅ (m-1)! + m ⋅ (m-1)! – n ⋅ (m-1)! m ⋅ (m-1)! m! = —————————————— = ———————— = ————— (m-n)! ⋅ n! (m-n)! ⋅ n! (m-n)! ⋅ n!                                                                                                                              Pascal’s Triangle Blaise Pascal was a 17th century French mathematician and philosopher who collaborated with Pierre de Fermat to develop the mathematics of probability.  A lot of probability is calculating the odds of an event by counting all the combinations in which it occurs.  Pascal also used mathematical functions in which the coefficients matched the combinations. Pascal also defined the process of mathematical induction that is extremely useful in proving an endless, repetitive process, like the list of combinations.  Pascal’s triangle is shown below as it is usually represented.  It should look familiar. This information is from Wikipedia.             Table of Cardinalities   n=         0 1 2 3 4 5 m=0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 1             Epilog When I first learned about combinations, I was introduced to Pascal’s triangle and the basic formula for counting combinations. The emphasis was on counting combinations over constructing them. When I saw that two combinations from the previous row, working down, summed to a combination on the next row and that the sum of the formulas produced the correct formula for the next row, I arrived at the misleading notion that the formulas drove the result. Instead, the formula is a natural extension of the physical properties of combinations. I might have understood combinations better from the beginning if i had asked one question: Why do the number of combinations sum up in this fashion? If I had asked this question from the beginning, I would have been a better mathematician. One final note. The formula for the number of combinations is not new, and it wasn’t new when I first saw it. The connection between the formula and the method of creating combination sets is new to me. I appreciate the formula more now, and I hope that I have conveyed that appreciation to you, the reader.