Transcript PowerPoint プレゼンテーション

4. Counting
• Combinatorics, the study of arrangements of objects, is an
important part of discrete mathematics.
4.1 The Basic of Counting
Basic Counting Principles
T heSum Rule
If a first taskcan be done in n1 ways and a second task in n2 ways ,
and if thesetaskscannotbe done at thesame time,then ther
e are
n1  n2 ways to do either task.
Example 1 suppose that either a member of the faculty or a student
in the department is chosen as a representative to university
committee. How many different choices for this representative if
there are 37 members of the faculty and 83 students?
Solution There are 37+83=120 possible ways to pick this
representative.
T hegeneralized versionof Sum Rule
Suppose that thetasksT1,T2 ,...,Tm can be done in n1,n2 ,...,nm ways,
respectively, and thesetaskscannotbe done at thesame time.
T hen thenumber of ways to do one of thesetasksis n1  n2    nm .
Example 2 A student can choose a computer science project from
one of three list. The three lists contain 23,15 and 19 possible project,
respectively. How many possible projects are there to choose from?
Solution There are 23+15+19=57 possible projects to choose from.
T heProduct Rule
Suppose thata procudurecan be brokendown into two tasks.If
thereare n1 ways to do thefirst taskand n2 ways to do thesecond task
after thefirst taskhas been done, then ther
e are n1n 2 ways to do procedure.
Example 2 The chairs are to be labeled with a letter and a positive
integer not exceeding 100. What is the largest number of chairs that
can be labeled differently?
Solution 26×100= 2600 chairs can be labeled differently.
T hegeneralized versionof Product Rule
Suppose thata procedureis carriedout by performingthe tasksT1,T2 ,...,Tm.
If taskTi can be done in ni ways after tasks T1,T2 ,...,Ti 1 havebeen done,
then thereare n1  n2   nm ways to carryout theprocedure.
Example 3 How many different bit strings are there of length seven?
Solution 27  128differentstringsof lengthseven.
Example 4 How many different license plates are available if each
plate contains a sequence of three letters followed by three digits?
Solution
26 26 26101010  17576000possible license plates.
4.3 Permutations and Combinations
Unordered collection
• Select 5 players from 10 members----How many possible choices?
• Prepare an ordered list of 4 plays to play the four singles matches
------How many possible choices?
Ordered collection
Permutations
•
A permutation of a set of distinct objects is an
ordered arrangement of these objects.
•
An r-permutation is an ordered arrangement of r
elements of a set.
Example 1 Let S={1,2,3}. The arrangement 3,1,2 is a
permutation of S. The arrangement 3,2 is a 2-permutation of S.
Theorem 1 The number of r-permutation of a set with n
distinct elements is P(n,r)=n(n-1)(n-2)…(n-r+1)=n!/(n-r)!
Proof
The first element can be selected from n elements.
The second element can be selected from the remaining n-1 elements.
The third element can be selected from the remaining n-2 elements.
..….
The rth element can be selected from the remaining n-(r-1) elements.
By using the product rule, P(n,r)=n(n-1)(n-2)…(n-r+1).
Example 2 How many different ways are there to select 4 different
players from 10 players on a team to play four tennis matches, where
the matches are ordered?
Solution: P(10,4)  10 9  8  7  5040.
Example 3 Suppose there are eight runners in a race. The winner
receives a gold metal, the second-place finisher receives a silver metal,
and the third-place finisher receives a bronze medal. How many
different ways are there to award these medals, if all possible outcomes
of the race can occur?
Solution: P(8,3)  8  7  6
Example 4 Suppose that a saleswoman has to visit eight different
cities.She must begin her trip in a specified city, but she can visit the
other seven cities in any order she wishes. How many possible orders
can the saleswoman use when visiting these cities?
Solution: P(7,7)  7! 5040
Combinations
•
An r-combination of elements of a set is an unordered
selection of r elements from the set.
Example 5 Let S={1,2,3,4}. Then {1,2,3} is a 3-combination from S.
The number of r-combinations of a set with n distinct elements is
denoted by C(n,r).
Example 6 We see that C(4,2)=6, since 2-combination of {a,b,c,d}
are the six subsets {a,b},{a,c},{a,d},{b,a},{b,c},{b,d}.
T heorem2
T henumber of r - combinations of a set of a set with n elements,
where n is a positiveintergerand r is na integer with 0  r  n, equals
n!
C (n, r ) 
.
r!(n  r )!
Proof: P(n,r), the r - permutations of theset, can be obtainedby
(1) formingtheC(n,r), the r - combinations of theset, and then
(2) orderingtheelementsin each r - combination, which can be done
in P(r,r) ways.
Consequently, P(n, r )  C (n, r )  P(r , r ).
P(n, r ) n! /(n  r )!
n!
T hisimplies thatC (n, r ) 


.
P(r , r ) r! /(r  r )! r!(n  r )!
Example 7 How many ways are there to select 5 players from a 10member tennis team to make a trip to a match at another school?
10!
Solution C (10,5) 
 252 .
5!5!
Example 8 How many ways are there to select a committee to
develop a discrete mathematics course at a school if the committee is
to consist of 3 faculty members from the mathematics department
and 4 from the computer science department, if there are 9 faculty
members in the mathematics department and 11 of the computer
science department?
Solution By theproduct rule, theanswer is theproduct of thenumber
of 3 - combinations of a set with9 elementsand thenumber of
4 - combinations of a set with11elements.
T herefore,thenumber of ways to select thecommitteeis
9! 11!
C (9,3) C (11,4) 

 84  330  27720.
3!6! 4!7!
4.4 Discrete Probability
Finite Probability
• Experiment: a procedure that yields one of outcomes.
• Sample space of the experiment S: the set of possible outcomes.
• Event E: a subset of the sample space.
Definition 1. The probability of an event E, which is a subset of a
finite sample space S of equally likely outcomes, is p(E)=|E|/|S|.
Example 1 An urn contains 4 blue balls and 5 red balls. What is
the probability that a ball chosen from the urn is blue?
Solution
• Experiment: Chose a ball from the urn.
• Sample space S = {b,b,b,b,r,r,r,r,r}. |S| = 9.
• Event E = {b,b,b,b}. |E| = 4
There are 9 possible outcomes, and 4 of them produce a blue ball.
Hence, the probability that a blue ball is chosen is P(E) = |E|/|S|= 4/9.
Example 2 What is the probability that when two dice are rolled,
the sum of the numbers on the two dice is 7?
Solution
• Experiment: Roll two dice.
• Sample space S = {(x,y) | 1 ≤ x,y ≤ 6}. |S| = 6×6=36.
• Event E = { (x,y) | x + y = 7}. |E| = 6.
There are 36 possible outcomes. Among them there 36 successful
outcomes: (1,6),(2,5),(3,4),(4,3),(5,2),(6,1）. Hence, the probability
is P(E) = |E|/|S| = 6/36=1/6．
Example 3 In a lottery, players win a large prize when they pick
four digits that match, in the correct order, four digits selected by a
random mechanical process. A smaller prize is won if only three
digits are matched. What is the probability that a player wins the
large prize? What is the probability that a play wins the small prize?
Solution
Suppose that the 4 digits for the large prize are (u,v,x,y).
• Experiment: Select 4 digits.
• Sample space S = {(a,b,c,d) | 0 ≤ a,b,c,d≤ 9}. |S| = 10×10×10×10
• Event 1 (large prize) E1 = { (u,v,x,y)}. |E| = 1.
Event 2 (smaller prize) E2 = { (a,b,c,d) | a ≠ u or b ≠ v or c ≠ x or d ≠ y}
|E2| = 9 + 9 +9 + 9 = 36
(1) There are 10000 to choose four digits. Hence, the probability that
a player wins the large prize is P(E1) = |E1|/|S| = 1/10000.
(2) To win the small prize, exactly one digit must be wrong to get
three digits correct. There are 36 ways to choose four digits like this.
Hence, the probability that a player wins the small prize is P(E2) =
|E2|/|S| = 36/10000=0.0036.
Example 4 There are lotteries that award enormous prizes to
people who correctly choose a set of six numbers out of the first n
positive integers, where n between 30 and 50. What is the
probability that a person picks the correct six numbers out of 40?
Solution
Suppose that the 6 numbers from 1 to 40 for the prize are {u,v,w,x,y,z}.
• Experiment: Select 6 numbers from 1 to 40.
• Sample space S = {{a,b,c,d,e,f} | 0 ≤ a,b,c,d,e,f ≤ 40}. |S| = C(40,6)
• Event 1 (large prize) E = { {u,v,w,x,y,z} }. |E| = 1.
The total number of ways to choose 6 numbers out of 40 is P(E) =
|E|/|S| = C(40,6)=40!/(34!6!)=3838380. Hence, the probability is
1/3838380.
Example 5 Find the probability that a hand of five cards in
poker contains three cards of one kind (same kind of character: 2,
3, …, K, A).
Solution
• Experiment: Pick 5 cards from 52 cards.
• Sample space S = {{a,b,c,d,e} | a,b,c,d,e are picked from 52 cards}.
|S| = C(52,5)
• Event E = { {a,b,c,d,e} | three of them are same kind}.
|E| = C(13,1)C(4,3)C(49,2).
The probability is P(E) = |E|/|S| = C (13,1)C (4,3)C (49,2) / C (52,5).