Transcript Section 4.1

Section 4.1
Basics of Counting
1
Basic Counting Principles:
Sum Rule
• Suppose you have two tasks to perform:
– The first task can be done in n1 ways;
– The second task can be done in n2 ways;
– If the two tasks can’t be done simultaneously,
then there are n1 + n2 ways to do either task
• Application of sum rule is pretty obvious:
add up the number of variations to arrive at
the total, which is your answer
• Can be extended to more than 2 tasks
2
Example 1 (using sum rule)
• Suppose one CS major or one engineering
major is eligible for the prestigious Sheller
scholarship
• Suppose there are 20 CS majors and 15
engineering majors to choose from - how
many choices are there for the scholarship?
• 20 + 15 = 35 possible choices
3
Example 2 (using sum rule)
What is the value of k after the following code is executed?
k = 0;
for (int i1=0; i1<n1; i1++)
k++;
for (int i2=0; i2<n2; i2++)
k++;
.
.
.
for (int im=0; im<nm; im++)
k++;
4
Example 2
•
•
•
•
Initial value of k is 0
There are m loops
Each iteration adds 1 to k
Let Ti = task of traversing the ith loop; can
be done ni ways, since traversal is done ni
times
• Since no 2 tasks can be done at once, final
value of k, which is the number of ways to
do Ti, where i = 1 … m is:
n1 + n2 + … + n m
5
Sum rule & sets
• If A1, A2, … , Am are disjoint sets:
A1  A2  …  Am = 
• Then the number of elements in the union
of these sets = the sum of the number of
elements in each set:
|A1  A2  …  Am| = |A1| + |A2| + … + |Am|
6
Basic Counting Principles:
Product Rule
• Suppose a procedure can be broken down
into 2 tasks, with n1 ways to do the first task
and n2 ways to do the second task
• After the first task is done, there are n1n2
ways to the do the procedure
• Can extend product rule as sum rule was
extended - in a procedure consisting of tasks
T1, T2, … Tm, each of which can be done n
ways, there are n1*n2* … *nm ways to carry
out the procedure
7
Example 3 (using product rule)
• Chairs in an auditorium are to be labeled with a
letter and a number between 1 and 100 - what is
the largest number of chairs that can be labeled
uniquely?
• Two tasks:
– assign one of 26 letters
– assign one of 100 integers
• By product rule, there are 26*100 different ways a
chair can be labeled - so there are 2600 unique
labels
8
Example 4 (using product rule)
• How many bit strings of length 8 are there?
• There are 2 possible values for each bit
• So there are 2*2*2*2*2*2*2*2 or 28 (256)
different bit strings
9
Example 5 (using product rule)
• How many different social security numbers
are possible?
– A SSN has 9 digits
– Each digit has one of 10 possible values
– So there are 109, or 1 billion possible social
security numbers
10
Example 6 - counting functions
• How many functions are there from a set
with m elements to one with n elements?
– The n elements in the codomain correspond to
each of m elements in the domain
– So there are n*n* … * n = nm functions from a
set with m elements to one with n elements
11
Example 7 - counting one-to-one
functions
• How many one-to-one functions are there from
a set with m elements to one with n elements?
– If m>n there are no one-to-one functions - so let m
<= n
– Suppose elements in domain are a1, a2, … am; there
are n ways to choose value of function at a1
– Since the function is one to one, the number of
choices for a2 are n-1
12
Example 7
• In general, the value at ak can be chosen in
n-(k+1) ways
• By the product rule, there are:
n(n-1)(n-2)*…*(n-m+1)
one-to-one functions from a set of m
elements to a set of n elements
13
Example 8 - assigning telephone
numbers
• Phone numbers in North America are
specified by a numbering plan:
– 10 digits, with 3-digit area code, 3-digit office
code, and 4-digit station code
– Some of these sequences are restricted to digits
1-9 or 0-1, while others may be 0-9
– If x=0..9, y=0..1 and n=2..9
• the plan in place until the 1960s was nyx-nnx-xxxx
• the current plan is: nxx-nxx-xxxx
14
Example 8
• How many unique phone numbers are possible
under each plan?
• Old plan:
n y x n n x x x x x
8*2*10*8*8*10*10*10*10*10
= 1,024,000,000
• New plan:
n x x n x x x x x x
8*10*10*8*10*10*10*10*10*10
= 6,400,000,000
15
Product rule & nested loops
What is the value of k after the following code is executed?
k = 0;
for (int i1=0; i1<n1; i1++)
for (int i2=0; i2<n2; i2++)
.
.
.
for (int im=0; im<nm; im++)
k++;
By the product rule,
value of k is:
n1*n2* … *nm
16
Product rule & sets
• If A1, A2, … Am are finite sets then the
number of elements in the Cartesian product
of the sets is the product of the number of
elements in each set:
|A1 x A2 x … x Am| = |A1| x |A2| x … x |Am|
17
Example 9: Combining sum rule
and product rule
• Suppose each user on a computer system
has a 6-8 character password, according to
the following rules:
– each character is an uppercase letter or digit
– there must be at least 1 digit per password
• How many possible unique passwords are
there?
18
Example 9
• Let P = total number of passwords:
– P6: total number with 6 characters
– P7: total number with 7 characters
– P8: total number with 8 characters
• By the sum rule, P = P6+P7+P8
19
Example 9
• To find P6, P7 and P8:
– Find the number of strings of letters and digits
that are n characters (including those with no
digits)
– Subtract from this the number of n-character
strings with no digits
– Result is number of n-character strings with at
least one digit
20
Example 9
• By the product rule, the number of strings with 6
characters is: (10 + 26)6:
– 10 possible digits
– 26 possible letters
– 6 positions in the string
• The number of strings with no digits is 266
• So the number of 6-character strings with at least
one digit is: P6 = 366 - 266 = 1,867,866,560
21
Example 9
• By the same logic,
– P7 = 367 - 267 = 70,332,353,920
– P8 = 368 - 268 = 208,827,064,567
• And P, which is P6 + P7 + P8 =
2,684,483,063,360
22
Example 10
• How many strings of 3 decimal digits do not contain the
same digit 3 times?
• Let D=total number of 3-digit strings
– product rule says D=10*10*10=1000
– Let D0 = total number of 3-digit strings containing just 0’s there is one of these
– Similarly, D1=1, D2=1, D3=1, etc.
• By the sum rule, the number of 3-digit strings not
containing the same digit 3 times is: D - (D0+D1+…+D9)
= 1000-10 = 990
23
Example 11
• How many strings of 3 decimal digits end
with an even digit?
• Using the product rule, where each “D”
below represents the number of possible
values for one digit of the string:
D1 * D2 * D3 = 10 * 10 * 5 = 500
24
Example 12
• How many strings of 3 digits contain
exactly 2 digits that are 4s?
• There are 3 ways this could occur: x44, 4x4,
or 44x
• The value of x could be any of the other 9
digits
• By the product rule, the number of possible
strings is 3 * 9, or 27
25
Principle of Inclusion/Exclusion
• If two tasks can be done at the same time,
can’t simply use the sum rule to count the
number of ways to do the tasks, because the
ways to do both tasks at once will be
counted twice
• To find the correct value, add the number of
ways each task can be done, then subtract
the number of ways to do both at once
26
Example 13
• How many 8-bit strings either start with a 1 or end with
2 0s?
– By the product rule, there are 27 (128) ways to form an 8-bit
string that starts with 1
– By the same logic, there are 26 (64) ways to form an 8-bit
string that ends with 2 0s
– Finally, there are 25 (32) ways to form an 8-bit string that
starts with 1 and ends with 2 0s
– So, to form a string that starts with 1 or ends with 2 0s (but
not both), there are 128+64-32 = 160 possible ways
27
Sets and the inclusion/exclusion
principle
• The number of elements in the union of two
sets is the sum of the number of elements in
both sets minus the number of elements in
the intersection of the sets:
|A1  A2| = |A1| + |A2| - |A1  A2|
28
Tree diagram
• Graphical representation that can be used to
help solve a counting problem
• For example, the diagram on the next slide
can be used to determine the number of bit
strings with length 4 that do not have 2
consecutive 1s
29
Tree diagram
We start with the
two possibilities
for the first digit (0 or 1)
If the first digit is 1, the
1
second must be 0
On the other hand,
if the first is 0,
•
the next could be
either 0 or 1
For the third digit,
0
there are 6 possible
paths
1
0
0
0
0
1
1
0
0 The number
of possibilities
1 for the 4th
digit gives us
0 the overall
1 result - there
are 8 different
0 ways to form
a 4-digit bit
0 string that does
1 not contain
consecutive 1s
0
30
Section 4.1
Basics of Counting
-ends-
31