### 5.1e

```The Basics of Counting:
Selected Exercises
Sum Rule Example
There are 3 sizes of pink shirts & 7 sizes of blue shirts.
How many types of shirts are there, if a shirt type is a
shirt of a particular color in a particular size?
Pink
Blue
2
Sum Rule
A  B =   |A  B| = |A| + |B|.
A
B
3
Sum Rule Generalization
Let { S1, S2, …, Sn } be a partition of S.
Then, | S | = | S1 | + | S2 | + … + | Sn |.
When using the sum rule,
1. Check 1: Have I partitioned S?
1. Are the subsets pairwise disjoint?
2. Is their union equal to S?
2. Check 2: What equivalence relation corresponds to my partition?
4
Product Rule
Let A be a set of elements constructed in 2 stages.
• Stage 1 has n1 possible outcomes.
• Stage 2 has n2 possible outcomes.
Then, | A | = n1n2.
5
Product Rule Example
• A store sells pink shirts & blue shirts;
each comes in small, medium, & large.
• How many types of shirts are there?
A shirt type can be described as an ordered pair:
(color, size).
6
Product Rule: Counting Ordered Pairs
Let A be a set of objects that are constructed (described) in 2 stages.
•
Let S be the set of values from stage 1
•
Let T be the set of values from stage 2
Then, | A | = | S | x | T |.
An element of A can be described as an ordered pair (a, b),
where a  S & b  T.
7
Product Rule Example
How many sequences of 2 distinct letters are there from
{ a, e, i, o, u } ?
1.
There are 5 ways to select the 1st letter in the
sequence.
2.
There are 4 ways to select the 2nd letter in the
sequence.
The set of values in stage 2 depends on which letter
was selected in stage 1.
The size of the set of values in stage 2 does not depend
on which letter was chosen in stage 1.
8
Product Rule: Counting Ordered Pairs
The product rule is a special case of the sum rule: When
1. { S1, S2, …, Sn } is a partition of A
2. | Si | = | Sj |, for 1 ≤ i, j ≤ n
The sum rule reduces to the product rule:
| S1 | + | S2 | + … + | Sn | = n| S1 |.
9
Exercise 10
How many bit strings are there of length 8?
10
Exercise 10
How many bit strings are there of length 8?
Use the product rule: Count the bit strings of length 8 by
decomposing the process into 8 stages:
count the possibilities for:
the 1st bit (2),
the 2nd bit (2),
…,
the 8th bit (2).
The product: 28 = 256 different bit strings.
11
Exercise 20
How many positive integers < 1000
1. Are divisible by 7?
12
Exercise 20
How many positive integers < 1000
1. Are divisible by 7?
└
999/7 ┘ = 142.
2. Are divisible by 7 & 11?
(Use a Venn diagram)
13
Exercise 20
How many positive integers < 1000
1. Are divisible by 7?
└
999/7 ┘ = 142.
2. Are divisible by 7 & 11?
└
999/(7.11) ┘ = 12.
3. Are divisible by 7 but not by 11?
(Use a Venn diagram)
14
Exercise 20
How many positive integers < 1000
1. Are divisible by 7?
└
999/7 ┘ = 142.
2. Are divisible by 7 & 11?
└
999/(7.11) ┘ = 12.
3. Are divisible by 7 but not by 11?
1. Count the # divisible by 7;
2. Subtract the # divisible by 7 & 11;
.11)
999/7
999/(7
└
┘ └
┘ = 142 – 12 = 130.
15
Exercise 20 continued
4. Are divisible by 7 or 11?
(Use a Venn diagram)
16
Exercise 20 continued
4. Are divisible by 7 or 11?
We want property A or property B: use inclusion-exclusion:
1. Count the # that are divisible by 7;
2. Add the # that are divisible by 11;
3. Subtract the # that are divisible by both;
└
999/7 ┘ + └ 999/11 ┘ – └ 999/(77) ┘ = 142 + 90 – 12.
7
11
17
Exercise 20 continued
5. Are divisible by exactly one of 7 & 11?
18
Exercise 20 continued
5. Are divisible by exactly one of 7 & 11?
What region of the Venn diagram represents the answer?
Count the symmetric difference: (union – intersection)
1. Count the # that are divisible by 7 or 11;
└
999/7 ┘ + └ 999/11 ┘ – └ 999/(7.11) ┘ = 142 + 90 – 12 =220.
2. Subtract the # that are divisible by both;
└
999/(7.11) ┘ = 12.
7
11
19
Exercise 20 continued
6. Are divisible by neither 7 nor 11?
What region of the Venn diagram represents the answer?
20
Exercise 20 continued
6. Are divisible by neither 7 nor 11?
What region of the Venn diagram represents the answer?
1. Count the universe (999).
2. Subtract the # that is divisible by 7 or 11 (220) giving
779.
7
11
21
Exercise 20 continue
7. Have distinct digits?
22
Exercise 20 continue
7. Have distinct digits?
Use the sum rule to decompose the problem into counting
1. The # of 1-digit numbers: 9
2. The #vof 2-digit numbers with distinct digits:
Use the product rule:
1. Count the # of ways to select the 10s digit: 9
2. Count the # of ways to select the unit digit: 9
3. There are 9 . 9 = 81 distinct 2-digit numbers.
3. The # of 3-digit numbers with distinct digits:
Use the product rule:
1. Count the # of ways to select the 100s digit: 9
2. Count the # of ways to select the 10s digit: 9
3. Count the # of ways to select the unit digit: 8
4. There are 9 . 9 . 8 = 648 distinct 3-digit numbers.
The overall answer is 9 + 81 + 648 = 738.
23
Alternate approach
– Make a 3-level tree of 3-digit numbers
• Top
level (100s digit): branch: 0 vs. !0
• Middle level (10s digit): branch: 0 vs. !0
• Bottom level (1s digit):
branch: 0 vs. !0
– Add the solutions for the branches
representing 3-digit numbers with distinct
digits.
24
1. 000: Invalid
2. 00X: 9
3. 0X0: 9
4. 0XY: 9 x 8 = 72
5. X00: Invalid
6. X0Y: 9 x 8 = 72
7. XY0: 9 x 8 = 72
8. XYZ: 9 x 8 x 7 = 504
Sum = 738
25
Sara’s approach
Count complement set; subtract from 999.
Sum rule:
• Exactly 2 digits the same:
– 2-digit numbers: 9
– 3-digit numbers:
» No “0”: XYY | YXY | YYX: 9 x 8 x 3
» 1 “0”: X0X | XX0: 9 x 2
» 2 “0”: X00: 9
• Exactly 3 digits the same: XXX: 9
Sum: 9 + 216 + 18 + 9 + 9 = 261; 999 – 261 = 738
26
Exercise 30
How many strings of 8 English letters are there:
a) If letters can be repeated?
27
Exercise 30
How many strings of 8 English letters are there:
a) If letters can be repeated?
Use product rule: (26)8
b) If no letter can be repeated?
28
Exercise 30
How many strings of 8 English letters are there:
a) If letters can be repeated?
Use product rule: (26)8
b) If no letter can be repeated?
Use product rule: 26 . 25 . 24 . 23 . 22 . 21 . 20 . 19
29
Exercise 30
How many strings of 8 English letters are there:
a) If letters can be repeated?
Use product rule: (26)8
b) If no letter can be repeated?
Use product rule: 26 . 25 . 24 . 23 . 22 . 21 . 20 . 19
Use product rule: 1 . (26)7
30
Exercise 30
How many strings of 8 English letters are there:
a) If letters can be repeated?
Use product rule: (26)8
b) If no letter can be repeated?
Use product rule: 26 . 25 . 24 . 23 . 22 . 21 . 20 . 19
Use product rule: 1 . (26)7
Use product rule: 1 . 25 . 24 . 23 . 22 . 21 . 20 . 19
e) That start & end with X, if letters can be repeated?
31
Exercise 30
How many strings of 8 English letters are there:
a) If letters can be repeated?
Use product rule: (26)8
b) If no letter can be repeated?
Use product rule: 26 . 25 . 24 . 23 . 22 . 21 . 20 . 19
Use product rule: 1 . (26)7
Use product rule: 1 . 25 . 24 . 23 . 22 . 21 . 20 . 19
e) That start & end with X, if letters can be repeated?
Use product rule: 1 . 1 . (26)6
32
Exercise 30 continued
f) That start with the letters BO, if letters can be repeated?
33
Exercise 30 continued
f) That start with the letters BO, if letters can be repeated?
Use product rule: 1 . 1 . (26)6
g) That start & end with the letters BO, if letters can be
repeated?
34
Exercise 30 continued
f) That start with the letters BO, if letters can be repeated?
Use product rule: 1 . 1 . (26)6
g) That start & end with the letters BO, if letters can be
repeated?
Use product rule: 1 . 1 . 1 . 1 . (26)4
h) That start or end with the letters BO, if letters can be
repeated?
35
Exercise 30 continued
h) That start or end with letters BO, if letters can be
repeated?
Use inclusion-exclusion:
repeated: (26)6
b) That end with the letters BO, if letters can be repeated:
(26)6
c) Subtract those that start and end with the letters BO, if
letters can be repeated: (26)4
Overall answer: 2 . (26)6 - (26)4
Start
w/ BO
End
w/ BO
36
Exercise 40
How many ways can a wedding photographer arrange 6
people in a row from a group of 10, where the bride &
groom are among these 10, if
a) The bride is in the picture?
37
Exercise 40
How many ways can a wedding photographer arrange 6
people in a row from a group of 10, where the bride &
groom are among these 10, if
a) The bride is in the picture?
Use the product rule:
a) Pick the position of the bride: 6
b) Place the remaining 5 people from left to right in the
remaining positions (use the product rule to do this):
9 . 8. 7 . 6 . 5
Overall answer is 6 . 9 . 8. 7 . 6 . 5.
38
Exercise 40 continued
b) Both the bride & groom are in the picture?
39
Exercise 40 continued
b) Both the bride & groom are in the picture?
Use the product rule:
a) Pick the bride’s position: 6
b) Pick the groom’s position: 5
c) Place 4 people from the remaining 8 in the remaining 4
slots, from left to right: 8 . 7 . 6 . 5.
The overall answer is 6 . 5 . 8 . 7 . 6 . 5.
40
Exercise 40 continued
c) Exactly 1 of the bride & groom is in the picture?
41
40 continued
c) Exactly 1 of the bride & groom is in the picture?
(symmetric difference of what?)
1. Pick either the bride or the groom: 2.
2. Place that person in the picture: 6.
3. Place remaining 5 from remaining 8 people:
P(8, 5) = 8 . 7 . 6 . 5 . 4.
The overall answer is 2 . 6 . 960 = 80,640.
42
Exercise 50
– A variable name in C can have uppercase & lowercase letters,
digits, or underscores.
– The name’s 1st character is a letter (uppercase or lowercase), or
an underscore.
– The name of a variable is determined by its 1st 8 characters.
How many different variables can be named in C?
43
Exercise 50
A variable name in C can have uppercase & lowercase letters, digits,
or underscores.
The name’s 1st character is a letter (uppercase or lowercase), or an
underscore.
The name of a variable is determined by its 1st 8 characters.
How many different variables can be named in C?
Use the sum rule to count the # of variable names of i characters,
for i = 1, 2, …, 8.
The overall answer is the sum of these numbers.
44
Exercise 50 continued
Use the product rule to count the # of names of a fixed size.
Let the name have i characters.
1.
The # of ways to pick the 1st character is 2 . 26 + 1 = 53.
2.
The # of ways to pick subsequent characters is 53 + 10.
The # of ways to pick the name is 53 . (63)i-1.
The overall answer is Σi=[1,8] 53 . (63)i-1 ≈ 2.1 x 1014.
45
End
46
Product Rule: Counting Ordered Pairs
•
Let A be a set of objects constructed (described) in 2 stages.
•
Let S be the set of values from stage 1.
•
If a  S is selected in stage 1, let Ta be the set of values for stage 2.
•
Essentially, A = { ( a, b ) | a  S and b  Ta }.
•
To use the product rule, for all a, b  S, | Ta | = | Tb |.
(Illustrate S and Ta with previous examples)
The product rule is a special case of the sum rule: When
1.
{ S1, S2, …, Sn } is a partition of A
2.
| Si | = | Sj |, for 1 ≤ i, j ≤ n
The sum rule reduces to the product rule: | S1 | + | S2 | + … + | Sn | = n| S1 |.
47
Characters
• .≥≡~┌
┐
└ ┘
• ≈
• 
•  Ω Θ
• Σ
• 
48
Exercise 20 continue
8. Have distinct digits and are even?
49
Exercise 20 continue
8. Have distinct digits and are even?
Easier to:
1.
count the number that have distinct digits (738)
2.
subtract those that are odd:
1. 1-digit: 5
2. 2-digit: 40
1. 5 ways to pick the unit digit
2. 8 ways to pick the 10s digit (nonzero)
3. 3-digit: 320
1. 5 ways to pick the unit digit
2. 8 ways to pick the 100s digit (nonzero)
3. 8 ways to pick the 10s digit
The total that have distinct digits & are odd is 5 + 40 + 320 = 365.
The overall answer is 738 – 365 = 373.
50
20 continued
The hard way: Use the sum rule directly:
1. 1-digit: 4
2. 2-digit:
low-order digit: 0 is picked: 1
high-order digit:
0 is not picked: 4
8
9
9
+
32 = 41
51
20 continued
3. 3-digit:
low-order digit:
0 is picked: 1
0 is not picked: 4
high-order digit:
9
8
middle digit:
8
8
72 + 256 = 328
The overall answer is 4 + 41 + 328 = 373.
52
40 continued
c) Exactly 1 of the bride & groom is in the picture?
1. There are 6 . 9 . 8 . 7 . 6 . 5 ways for the bride to be in the picture.
2. There are 6 . 5 . 8 . 7 . 6 . 5. ways for the bride and groom to be in
the picture.
3. The number of ways for the bride only to be in the picture is
6 . 9 . 8 . 7 . 6 . 5 - 6 . 5 . 8 . 7 . 6 . 5 = 6 . 8 . 7 . 6 . 5 (9 – 5) = 40,320.
4. There are the same number of ways for the groom only to be in the
picture (a 1-to-1 correspondence between bride-only & groom-only)
The overall answer is 2 . 40,320.
53
40 alternate answer for part c
c) Exactly 1 of the bride & groom is in the picture?
Use the product rule:
1. Pick the bride or groom to be in the picture: 2.
2. Count the number of ways to fill out that picture.
Use the product rule:
1. Place the bride/groom: 6
2. Fill in the other positions from left to right: 8 . 7 . 6 . 5 . 4.
The overall answer is 2 . 6 . 8 . 7 . 6 . 5 . 4 = 80,640.