Combinations (Order Is Not Important)

 

Suppose we want to count the number of r-element subsets in an n-element set. For example, if S = {a, b, c, d}, then there are four 3-element subsets of S:

 

{a, b, c}, {a, b, d}, {a, c, d}, and {b, c, d}.

 

Is there a formula for the general case?

The answer is yes. An easy way to see this is to first count the number of r-element permutations of the n elements, which is given by the formula

 

.

 

Now each r-element subset has r! distinct r-element permutations, which we have included in our count P(n, r). How do we remove the redundant permutations from the count? Let C(n, r) denote the number of r-element subsets of an n-element set. Since each of the r-element subsets has r! distinct permutations, it follows that r! × C(n, r) = P(n, r). Now divide both sides by r! to obtain the formula

 

                        .                                                 (2.5)

 

EXAMPLE 4. If S = {a, b, c, d, e}, then all the three-element subsets of S are listed as follows:

{a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e},

{a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

 

There are 10 such subsets, and we can verify the number by the calculation

 

.

 

The expression C(n, r) is usually said to represent the number of combinations of n things taken r at a time. With combinations, the order in which the objects appear is not important. We count only the different sets of objects. The expression C(n, r) is often read "n choose r."

Notice how C(n, r) crops up in the following binomial expansion of the expression {x + y)4:

 

(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4 =

= C(4,0)x4 + C(4,1)x3y + C(4,2)x2y2 + C(4,3)xy3 + C(4,4)y4

 

Another useful way to represent C(n, r) is with the binomial coefficient symbol:

 

.

 

Using this symbol, we can write the expansion for (x + y)4 as follows:

 

.

This is an instance of a well-known formula called the binomial theorem, which can be written as follows, where n is a natural number:

 

                                                 .                                              (2.6)

 

The binomial coefficients for the expansion of (x + y)n can be read from the nth row of Table 6.1. The table is called  Pascal's triangle – after the philosopher and mathematician Blaise Pascal (1623-1662). However, the triangle was known prior to the time of Pascal in China, India, the Middle East, and Europe. Notice that any interior element is the sum of the two elements above and to its left.

 

Table 2.1 – Pascal's triangle.

 

n

0

1

2

3

4

5

6

7

8

9

10

0

0

 

 

 

 

 

 

 

 

 

 

1

1

1

 

 

 

 

 

 

 

 

 

2

1

2

1

 

 

 

 

 

 

 

 

3

1

3

3

1

 

 

 

 

 

 

 

4

1

4

6

4

1

 

 

 

 

 

 

5

1

5

10

10

5

1

 

 

 

 

 

6

1

6

15

20

15

6

1

 

 

 

 

7

1

7

21

35

35

21

7

1

 

 

 

8

1

8

28

56

70

56

28

8

1

 

 

9

1

9

36

84

126

126

84

36

9

1

 

10

1

10

45

120

210

252

210

120

45

10

1

 

But how do we really know that the following statement is correct?

The element in the nth row and kth column of the triangle is .                (2.7)

Let's continue our discussion about combinations by counting bags of things rather than sets of things. Suppose we have the set A = {a, b, c}. How many three-element bags can we construct from the elements of A? We can list them as follows:

 

[a, a, a], [a, a, b], [a, a, c], [a, b, c], [a, b, b],

[a, c, c], [b, b, b], [b, b, c], [b, c, c], [c, c, c].

 

So there are 10 three-element bags constructed from the elements of {a, b, c}. Let's see if we can find a general formula for the number of k-element bags that can be constructed from an n-element set. For convenience, we'll assume that the n-element set is A = {1, 2, ..., n}. Suppose that b = { x1, x2, x3, . . . , xk} is some k-element bag with elements chosen from A, where the elements of b are written so that x1 < x2 < ... < xk. This allows us to construct the following k-element set:

 

B= {x1, x2 + 1, x3 + 2, . . . , xk + (k - 1)}.

 

The numbers xi + (i - 1) are used to ensure that the elements of  B are distinct elements in the set C = {1, 2, . . . , n + (k - 1)}. So we've associated each k-element bag b over A with a k-element subset B of C. Conversely, suppose that {y1, y2, y3, . . . , yk} is some k-element subset of C, where the elements are written so that y1 ≤ y2 ≤  ... ≤  yk. This allows us to construct the k-element bag

 

{y1, y2-1, y3-2, . . . , yk-(k-1)},

 

whose elements come from the set A. So we've associated each k-element subset of  C with a k-element bag over A.

Therefore the number of k-element bags over an n-element set is exactly the same as the number of  k-element subsets of a set with n + (k - 1) elements. This gives us the following result:

 

Bag Combinations

 

The number of  k-element bags whose distinct elements are chosen from n n-element set is given by the following formula, where k and n are positive:

 

                                                                                                     (2.8) 

 

EXAMPLE 5. In how many ways can four coins be selected from a collection of pennies, nickels, and dimes? Let S = {penny, nickel, dime}. Then we need the number of four-element bags chosen from S. The answer is

 

 

EXAMPLE 6. In how many ways can five people be selected from a collection of Democrats, Republicans, and Independents? Here we are choosing five-element bags from a set of three characteristics {Democrat, Republican, Independent). The answer is