Transcript Basic Counting Principles

The Addition & Multiplication
Principles
The Addition Principle
If {S1, S2, . . . , Sn} is a partition of S,
then |S| = |S1| + |S2| + . . . + |Sn|.
• Example:
• Let {S1, S2} be a partition of S; |S1| = |S2| = 40.
• Then |S| = 80.
40
+
40
= 80
When A & B are not Disjoint
• {A - B, A  B, B - A} partition A  B:
• Every element is in exactly 1 part.
• Let |A-B| = 30, |A  B| = 10, & |B-A| = 30.
• |A  B| = |A - B| + |A  B| + |B - A| = 70.
30
10
30
= 70
Example
• In how many ways can we draw a heart or a
spade from an ordinary deck of cards?
• A heart or an ace?
• In how many ways can we get a sum of 4 or
8 when 2 distinguishable dice (say 1 is red,
1 blue) are rolled?
• Model “distinguishable” as an ordered pair.
• What about when the dice are
indistinguishable?
• Model “indistinguishable” as a set.
The Product Rule
• Let S1, S2, . . . , Sn be nonempty sets.
• | S1  S2  . . .  Sn | = | S1||S2| . . .  |Sn |.
b
a
(a,0)
(a,1)
(b,0)
c
(b,1)
S1 = {a, b, c}; S2 = {0, 1}
(c,0)
(c,1)
• Think of the product rule as creating a
composite object in stages S1, S2, . . . , Sn .
• Then there are | S1||S2| . . .  |Sn | different
composite objects.
• If 2 distinct dice are rolled, how many
outcomes are there?
• If 100 distinct dice are rolled, how many
outcomes are there?
Example
• Suppose the CCS tee shirt comes in 3
colors, and 4 sizes. How many different
kinds of CCS tee shirts are there?
• How many 3-digit numbers can be formed
from the digits {1, 2, 3, 4, 5, 6, 7, 8, 9}?
• How many 3-digit numbers can be formed
from the above set when no digit can be
repeated?
• How many license plates can be formed
from 3 letters followed by 4 digits?
• From 1, 2, or 3 letters, followed in each
case by 4 digits?
• From 1, 2, or 3 letters, followed in each
case by 4 digits, when the 4 digits,
interpreted as a number, is even?
Indirect Counting
• Count the elements of a set by computing
the size of its complement & subtracting
from size of the universe.
• How many nonnegative numbers < 109
contain the digit 1?
• The size of the universe is 109.
• The number of nonnegative numbers < 109 that
do not contain the digit 1 is 99.
• This includes numbers like 000000004, which is 4.
Example
• We draw a card from a deck & replace it
before the next draw. In how many ways can
10 cards be drawn so that the 10th card
matches at least 1 of the previous draws?
• There are 5210unrestricted 10 card draws.
• There are (52)(51)9 ways to draw 10 cards where
the 10th card does not match any previous:
• 1st pick the 10th card; pick the other 9 from the other
51 cards.
Example 2
• How many ways can 8 students be seated in a
row so that a certain pair are not adjacent?
• There are 8! seatings without restriction.
• The number of ways where the pair do sit
next to each other is (7)(2)6! = (2)7!
• Pick the position of the left seat of the pair (7);
• Pick the order of the pair (2);
• Order the other 6 people in the other 6 seats (6!).
One-to-one Correspondence
1) Note that the number of solutions to one
problem is in 1-to-1 correspondence with
those of another problem.
2) Count the number of solutions in the other
problem (which presumably is easier).
Example: To count the number of cows in a
field, simply count the number of cow legs
in the field and divide by 4.
Ok, a real example
• Suppose there are 101 players in a single
elimination tennis tournament.
• In such a tournament, if a player loses a
match, he is eliminated (i.e., shot).
• In every match, someone loses (no ties).
• The tournament proceeds in rounds.
• In round 1, there are 50 matches, &
someone gets a bye.
• In round 2, there are 25 matches, &
someone gets a bye.
• In round 3, there are 13 matches.
• In round 4, there are 6 matches, and
someone gets a bye.
• In round 5, there are 2 matches.
• In round 6, there is the final match.
• If there are 10,975 people in the
tournament, how many matches are needed?
• Observe that there is a 1-to-1
correspondence with matches and losers.
• A match eliminates 1 person from the
tournament.
• Thus, 10,975 - 1 matches are needed.
Attacking a problem
• Devising an overall counting strategy
usually is the hardest part.
• If it is unclear how to proceed, get concrete:
• Start to enumerate the possible outcomes - this
usually leads to some insight as to the structure
of the problem.
• Try a special case. For example, if the problem
is in terms of a parameter, n, try to solve it for n
= 2; then 3; then 4. Look for a pattern.
Characters
•
•
•
•
•
•





