Discrete Mathematics for Computer Science

440 CHAPTER 7 Counting and Combinatorics

To count the number of possible seating arrangements at a round table, consider the

case of 12 people. Suppose that one of the people is named Henry and that Henry's seat is

chair number 1. We number the remaining chairs clockwise around the table from Henry's

chair. There are P (11, 11) = 11! ways to seat the remaining 11 people in chairs 2 through

12. Counting the ways of seating people relative to Henry avoids counting arrangements
    that are considered to be the same. By a similar argument, it can be shown that the number
    of circular permutations of n people is just P(n - 1, n - 1) = (n - 1)!.

7.5.4 Combinations

A card game uses only Aces, Kings, and Queens from a deck, with four of each. Each card

of a given value is from one of four suits, called Clubs, Diamonds, Hearts, and Spades. At

the beginning of the game, each player is dealt three cards. How many different three-card

combinations can be dealt?

We solve this problem by answering two questions and then combining the answers to

those questions to find the final answer. The first question is how many ordered arrange-

ments are comprised of 3 of 12 cards? The answer to this question is P (12, 3). The second

question is how many ordered arrangements are generated by a single set of three cards?

For example, the two sets of choices of cards shown in Table 7.1 cannot be distinguished

from one another.

Table 7.1 Different Orders for Choosing Cards

Choice 1 Choice 2

Card 1 Ace of Spades King of Hearts

Card 2 Queen of Diamonds Ace of Spades

Card 3 King of Hearts Queen of Diamonds

The answer to this question is P(3, 3). Since the answer to the second question tells how

many times each set of three cards occurs as a different ordered arrangement, the answer

to the original question is P(12, 3)/P(3, 3).

We now define more formally the general notion illustrated in this example for count-

ing elements that are indistinguishable from one another.

Definition 2. Let n, r E N such that n > r > 0. An unordered selection of r elements

from an n element set is called a combination.

Example 4. List all the combinations of the set {a, b, c}.

Solution. The combinations will be of sizes 0, 1, 2, and 3. All combinations are 0,

{a}, {b}, {c}, {a, b), {a, c}, {b, c}, and {a, b, c}. 0

Let C(n, r) denote the number of combinations of r elements selected from a set of n

elements. Another common notation for C(n, r) is ("). Note that C(n, 0) is defined to be 1

for all n c N. C(n, r) is also called a binomial coefficient, because these numbers occur

as coefficients in the expansion of powers of binomials, such as (x + y)n. We will prove

this in Theorem 5 in Section 7.9.1.