Permutations and Combinations 441Theorem 2. Forn > r >0,
C(n, r) - (n,r)
P(r, r) (n - r)! r!
Proof. The number of r-permutations of an n-element set is P(n, r). An r-permutation
can be formed by choosing an r-element set without regard to order and then arranging
these elements in P (r, r) different ways. Therefore,
P(n, r) = C(n, r) • P(r, r)
C(n, r) = (n,r)
P(r, r)
n!
(n - r)! r! UCorollary 1: C(n, r) = C(n, n - r).
Proof C(n, r) is the number of ways of choosing r elements from an n-element set. Each
choice of r-elements determines a unique subset of n - r elements-namely, the comple-
ment of the set of elements chosen. Therefore, the function F (A) = A with A ranging over
the r-element subsets of an n-element set is well defined. It is easy to show this function
is 1-1 and onto using the fact that A = A (see Theorem 7 in Section 1.3.2 ). Therefore,
C(n, r) and C(n, n - r) count the same number of elements. U
You can also formulate a direct argument to prove Corollary 1 by using the identity
n! n!
(n - r)!r! (n - (n - r))!(n - r)!7.5.5 Poker Hands
A class of interesting examples that uses counting techniques involves poker hands. A
poker hand is a set of five cards dealt from a deck of^52 cards, divided into four suits (or-
dered as Clubs, Diamonds, Hearts, and Spades in increasing order), with each suit contain-
ing 13 cards with the values 2, 3, ...., 10, Jack, Queen, King, and Ace (listed in increasing
order for purposes of poker). The Ace can be either the highest or the lowest card in a hand.
The order in which the cards are dealt does not make a difference. For example, the two
hands shown in Table 7.2 are the same poker hand.
Table 7.2 Poker Hands
Order Dealt Name of Card Name of Card
1 Ace of Hearts Jack of Hearts
2 King of Spades 3 of Diamonds
3 4 of Clubs King of Spades
4 Jack of Hearts Ace of Hearts
5 3 of Diamonds 4 of Clubs