Transcript Counting3

Counting Techniques:
Permutations of Selected Elements
Addition Rule,
Difference Rule,
Inclusion/Exclusion Rule
1
Permutations of Selected Elements
 Typical situation: A chairman, a secretary and a
treasurer are to be chosen in a committee of 7
people.
• Question: In how many different ways can it be done?
Definition: An r-permutation of a set S of n
elements is an ordered selection of r elements
taken from S.
The number of all r-permutations of a set of n
elements is denoted P(n,r) .
 In the example above we want to find P(7,3).
How to compute P(n,r)
 Theorem: P(n,r) = n(n-1)(n-2)…(n-r+1)
or, equivalently,
n!
P(n, r ) 
(n  r )!
 Proof:
Forming an r-permutation of a set of n-elements
is an r-step operation:
 Step 1: Choose the 1st element ( n different ways).
 Step 2: Choose the 2nd element ( n-1 different ways).
…
 Step r: Choose the rth element (n-r+1 different ways).
Based on the multiplication rule,
the number of r-permutations is n∙(n-1)∙…∙(n-r+1) .
3
Examples of r-permutations
1. Choosing a chairman, a secretary and a treasurer
among 7 people:
P(7,3) = 7∙6∙5 = 210 .
2. Suppose Jim is already chosen to be the secretary.
Q: How many ways a chairman and a treasurer can
be chosen?
A: P(6,2) = 6∙5 = 30 .
3. In an instance of the Traveling Salesman Problem,
the total number of cities = 10;
this time the salesman is supposed to visit
only 4 cities (including the home city).
Q: How many different tours are possible?
A: P(9,3) = 9∙8∙7 = 504 .
4
The Addition Rule
• Suppose a finite set A equals the union of
k distinct mutually disjoint subsets A1, A2, …, Ak .
Then
n(A) = n(A1) + n(A2) + … + n(Ak)
• Example: How many integers from 1 through 999
do not have any repeated digits?
Solution: Let A = integers from 1 to 999
not having repeated digits.
Partition A into 3 sets:
A1=one-digit integers not having repeated digits;
A2=two-digit integers not having repeated digits;
A3=three-digit integers not having repeated digits.
Then n(A)=n(A1)+n(A2)+n(A3) (by the addition rule)
= 9 + 9∙9 +9∙9∙8 = 738. (by the multipl. rule)
The Difference Rule
• If A is a finite set and B is a subset of A,
then n(A-B) = n(A) – n(B) .
• Example: Assume that any seven digits can be used
to form a telephone number.
Q: How many seven-digit phone numbers
have at least one repeated digit?
Let A = the set of all possible 7-digit phone numbers;
B = the set of 7-digit numbers without repetition.
Note that BA .
Then A-B is the set of 7-digit numbers with repetition.
n(A-B) = n(A) – n(B)
(by the difference rule)
= 107 – P(10,7)
(by the multiplication rule)
= 107 – 10! / 3! = 10,000,000 – 3,628,800/6 =
= 10,000,000 – 604,800 = 9,395,200
6
The Inclusion/Exclusion Rule
for Two or Three Sets
If A, B and C are finite sets then
 n(A  B) = n(A) + n(B) – n(A  B)
A
B
 n(A  B  C) = n(A) + n(B) + n(C)
- n(A  B) – n(A  C) – n(B  C)
C
+ n(A  B  C)
A
B
7
Example on
Inclusion/Exclusion Rule (2 sets)
• Question: How many integers from 1 through 100
are multiples of 4 or multiples of 6 ?
• Solution: Let A=the set of integers from 1 through 100
which are multiples of 4;
B = the set of integers from 1 through 100
which are multiples of 6.
Then we want to find n(A  B).
First note that A  B is the set of integers
from 1 through 100 which are multiples of 12 .
n(A  B) = n(A) + n(B) - n(A  B) (by incl./excl. rule)
= 25 + 16 – 8 = 33 (by counting the elements
of the three lists)
Example on
Inclusion/Exclusion Rule (3 sets)
• 3 headache drugs – A,B, and C – were tested on 40
subjects. The results of tests:
23 reported relief from drug A;
18 reported relief from drug B;
31 reported relief from drug C;
11 reported relief from both drugs A and B;
19 reported relief from both drugs A and C;
14 reported relief from both drugs B and C;
37 reported relief from at least one of the drugs.
Questions:
1) How many people got relief from none of the drugs?
2) How many people got relief from all 3 drugs?
3) How many people got relief from A only?
Example on
Inclusion/Exclusion Rule (3 sets)
S
C
A
B
We are given: n(A)=23, n(B)=18, n(C)=31,
n(A  B)=11, n(A  C)=19, n(B  C)=14 ,
n(S)=40, n(A  B  C)=37
Q1) How many people got relief from none of the drugs?
By difference rule,
n((A  B  C)c ) = n(S) – n(A  B  C) = 40 - 37 = 3
10
Example on
Inclusion/Exclusion Rule (3 sets)
Q2) How many people got relief from all 3 drugs?
By inclusion/exclusion rule:
n(A  B  C) = n(A  B  C)
- n(A) - n(B) - n(C)
+ n(A  B) + n(A  C) + n(B  C)
= 37 – 23 – 18 – 31 + 11 + 19 + 14 = 9
Q3) How many people got relief from A only?
n(A – (B  C))
(by inclusion/exclusion rule)
= n(A) – n(A  B) - n(A  C) + n(A  B  C)
= 23 – 11 – 19 + 9 = 2