Permutations and Combinations
441
Theorem 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!
U
Corollary 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 complement 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 (ordered as Clubs, Diamonds, Hearts, and Spades in increasing order), with each suit containing 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
441
Theorem 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!
U
Corollary 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 complement 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 (ordered as Clubs, Diamonds, Hearts, and Spades in increasing order), with each suit containing 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