Transcript Section 5-2

SECTION 5.2
Simple Arrangements and
Selections
Aaron Desrochers and Ben Epstein
Tucker, Applied Combinatorics
1
Vocabulary
Permutation: an arrangement or ordering of n distinct
objects.
R-Permutation: an arrangement using r of n objects. P(n,r)
denotes the r-permutation on n objects.
In general, P(n,n) = n!
Therefore, P(n,r) = n(n-1)(n-2)…[n-(r-1)] = n!/(n-r)!.
So, P(6,2) = 6!/(6-2)! = 6!/4! = (6)(5)(4)(3)(2)(1) /
(4)(3)(2)(1) = (6)(5) = 30.
NOTE: P(n,n) = n! Since (n-n)! = 0! = 1.
So, P(4,4) = 4! = 24.
Tucker, Applied Combinatorics
2
Vocabulary
Combination: an unordered arrangement of n objects.
R-Combination: an unordered selection using r of n objects.
C(n,r) denotes the r-combination of n objects.
In general C(n,r) = n!/(r!(n-r)!).
This is easily derived using P(n,r), since rcombinations of n objects gives the number of unordered
arrangements, dividing P(n,r) by the total number of possible
arrangements of n (so let r = n) gives the total number of
unordered arrangements.
So C(n,r) = P(n,r) / P(n,n) = n!/(r!(n-r)!).
NOTE: A common notation for C(n,r) is
combination of n choose r objects.
Tucker, Applied Combinatorics
n
r
. We say the
3
Example 1
How many 5-card hands can be formed from a standard 52card deck?
First we must ask will the hands be ordered or unordered. In
this example let’s suppose we want unordered 5-card hands.
So it is simply
C(52,5) = 52!/[5!(52-5)!] = (52)(51)(50)(49)(48) /5!=
2,598,960 hands.
Tucker, Applied Combinatorics
4
Example 2
If a 5-card hand is chosen at random, what is the probability of
obtaining a flush (all cards having the same suit)?
• In this case order does not matter, so we will use the notion of
combinations.
• First, we must notice that there are 13 cards in every suit. Also, we have
4 suits to choose from, therefore (4)C(13,5) = 5148 ways to get a flush.
• The probability is found by dividing the number of ways of getting a
flush by the total number of possible hands, which we computed in the last
example.
•Therefore, the probability of a getting a flush is 5148/2,598,960 = .00198
or about .2%.
Tucker, Applied Combinatorics
5
Example 3
A committee of k people is to be chosen from a set of 7
women and 4 men. How many ways are there to form a
committee of 5 people, including 3 women and 2 men?
• We want 3 of the 7 women and 2 of the 4 men.
• There are 7 choose 3 ways of selecting the three women.
• There are 4 choose 2 ways of selecting the 2 men.
• The product of the two gives the total number of ways.
C(4,2)C(7,3) =
7!
4!
7!
4!



 210
3! 7  3! 2! 4  2 ! 3! 4 ! 2! 2 !
Tucker, Applied Combinatorics
6
Example 4
How many ways are there to form a committee of 4 people
with at least two women members?
• The trick with this question is dealing with the “at least”
part. This can be broken down as the sum of “picking exactly
2 women + picking exactly 3 women + picking exactly 4
women”.
• So, C(7,2)C(4,2) + C(7,3)C(4,1) + C(7,4)C(4,0) =
7!
4!
7!
4!
7!
4!





 301
2! 7  2 ! 2! 4  2 ! 3! 7  3! 1! 4  1! 4! 4  4 ! 0! 4  0 !
Tucker, Applied Combinatorics
This is equal to one
7
Example 5
The chromatic polynomial Pk(G) of graph G is the
polynomial in k that gives the number of k-colorings of
G. What is the chromatic polynomial of:
A complete graph K5 on five vertices (all vertices adjacent
to each other)
k-1
k
k-2
k-4
k-3
In a complete graph, each vertex must be a different color.
Thus, Pk(K5) = P(k,5), since there are k possible colors for
the first vertex, k-1 for the second choice, k-2 for the third
choice and so on.
Tucker, Applied Combinatorics
8
Example 5
• P(k,5) = k!/(k-5)!=k(k-1)(k-2)(k-3)(k-4)
(k 2  k )(k  2)(k  3)(k  4)
(k 3  3k 2  2k )(k 2  7 k  12)
k 5  10k 4  35k 3  50k 2  24k
This is the chromatic polynomial.
Tucker, Applied Combinatorics
9
Example 5 Continued
b) Find Pk(C4) where C4 is a circuit of length 4?
a
c
b
d
Let the vertices on the circuit C4 be named a, b, c, d with edges (a,b), (b,c), (c,d) and (d,a). We
break the computation of Pk(C4) into two cases, depending on whether or not a and c are given
the same color.
If a and c have the same color, there are k choices for the color of these two vertices. Then b
and d each must only avoid the common color of a and c --- k-1color choices each. So the
number of k-colorings of C4 in this case is k(k-1)^2.
If a and c have different colors, there are k(k-1) choices for the two different colors for a and
then c. Now b and d each have k-2 color choices. So in this case the total number of kcolorings of C4 is k(k-1)(k-2)^2.
Combining the two cases, we obtain Pk(C4) = k(k-1)^2 + k(k-1)(k-2)^2.
Tucker, Applied Combinatorics
10
Class Exercise 1
How many different 8-digit binary sequences are there with six
1’s and two 0’s?
Consider that we have 8 slots to fill given these two conditions.
Any six slots must be 1’s so C(8,6) gives the number of ways to fill any six
slots. Notice that we do not have to make any choices for the zeros because
they must go in the last two slots. So the solution is C(8,6) = 28.
It is important to note that the solution can be arrived at by selecting the slots
for the zeros. In this case C(8,2) = 28.
Note also that this is the compliment of C(8,6) and that they are equal.
So in general C(n,r) = C(n,n-r).
Tucker, Applied Combinatorics
11
Class Exercise 2
What is the probability that a 4-digit campus telephone
number has 2 digits the same and the other two digits
different?
Again consider filling the slots, only in this case we need
four of them.
• First we want to pick the slots. We need 2 slots to hold the
pair of identical numbers. These slots can be chosen in C(4,2)
ways.
• Note that we need not choose where the last two numbers
will go because their positions are forced.
Tucker, Applied Combinatorics
12
• Next, we need to choose the actual numbers. Certainly we have 10 digits
to choose from and we want just one for the identical pair so C(10,1) gives
us the number of ways to choose any digit.
• For the third digit we must select any digit that is not the same as the first,
so we have C(9,1). And similarly for the fourth C(8,1).
• The question asks for the probability so we must divide the product of all
of these combinations by the total number of possible ordered 4-digit phone
numbers.
• Using the slot method, we have 10 choices for the first slot, 10 for the
second, 10 for the third and 10 for the fourth. So 10^4 gives us the total
number of possible ordered phone numbers.
• The probability is then
[C(4,2)C(10,1)C(9,1)C(8,1)] / 10^4,
 4!  10!  9!  8! 
4
4

10

(4*3*10*9*8)

10





 10  9 !   9  8 !   8  7 ! 
4

2
!







54/125 = .432 = 43.2%
Tucker, Applied Combinatorics
13