Transcript Chapter 3.2 - Computer Science

Set, Combinatorics, Probability &
Number Theory
Mathematical Structures
for Computer Science
Chapter 3
Copyright © 2006 W.H. Freeman & Co.
MSCS Slides
Set, Combinatorics, Probability & Number Theory
Counting


Combinatorics: the branch of mathematics that deals with
counting things.
Counting problems can deal with infinite numbers, but usually
we’re interested in finding out how many members are present in
a finite set. For example:



Counting problems we’ve already looked at:



Section 3.2
If a man has 4 suits, 8 shirts and 5 ties, how many outfits can he put
together?
How many memory locations can be addressed with a 32-bit
address?
How many rows in a truth table with n variables?
How many subsets in the power set of a given set S?
Counting example: A child is allowed to choose one jellybean
out of two jellybeans, one red and one black, and one gummy
bear out of three gummy bears, yellow, green, and white. How
many different sets of candy can the child have?
Counting
1
Example: Multiplication Principle

Section 3.2
There are 23=6 or 32=6 possible outcomes as seen
from the following figures
Counting
2
Counting – the Multiplication Principle




Section 3.2
Multiplication Principle: If there are n possible outcomes for a
first event and m possible outcomes for a second event, then there
are n*m possible outcomes for the sequence of two events.
Hence, from the multiplication principle, it follows that for two
sets A and B
|AB| = |A|*|B|
Remember that AB is the set of ordered pairs where the first element
comes from A and the second from B. In this case, choose one thing
from A ( there are |A| choices) and one thing from B, with |B| choices.
In the example, A is the set of jelly beans, B is the set of gummy bears.
Counting
3
Counting – the Multiplication Principle


We can use induction to extend the multiplication principle:
If there are n1 possible outcomes (choices) for a first event, n2
possible outcomes for a second event, … nm possible outcomes
for the mth event, then there are n1*n2*…*nm possible outcomes
for the sequence of events.
Example: Number of locations addressable with 32 bits:




What if repetition is not allowed? Suppose we have 10 colored
balls. How many ways to arrange them in a row?
Now suppose we don’t use all the objects in the set. Consider
choosing three officers from a club that has 25 members? How
many ways can we do this?


Section 3.2
n=?
m=?
If no person can hold more than one office
If a person can hold more than one office.
Counting
4
Counting – The Addition Principle




Section 3.2
The multiplication principle applies when you have a
sequence of events, and for each event you have several
choices.
Other situations involve more than one event, but they
are disjoint, not separate. When we select one event we
rule out the others.
Example: buying a vehicle from a dealer who has 23
cars and 14 trucks. You have 23 + 14 = 37 possible
outcomes. First choose an event (buy car or buy truck)
and then choose one possibility.
Addition Principle: If A and B are disjoint events with
n and m possible outcomes, then the total number of
possible outcomes for event “AorB” is n + m.
Counting
5
Addition Principle


If A and B are disjoint sets, then |A  B| = |A| + |B| using the addition
principle.
Example 32 proves that if A and B are finite sets then
|A-B| = |A| - |A  B| and |A-B| = |A| - |B| if B  A
(A-B)  (A  B) = (A  B)  (A  B)
= A  (B  B)
=AU
=A

Also, A-B and A  B are disjoint sets, therefore using the addition
principle (see first bullet point above)
|A| = | (A-B)  (A  B) | = |A-B| + |A  B|


If B  A, then A  B = B

Section 3.2
Hence, |A-B| = |A| - |A  B|
Hence, |A-B| = |A| - |B|
Counting
6
Combining the Principles


Sometimes a counting problem uses both the
multiplication and addition principles.
Example: how many 4-digit numbers begin with the
digits 4 or 5?


Disjoint events: numbers starting with 4, numbers
starting with 5. TWO such events (addition principle)
Use multiplication principle to count number of 4-digit
numbers: for the first digit there is one choice.
• How many for the second digit? The third & fourth?


Section 3.2
Now count the number of 5 digit numbers in the same
way.
Now, use the addition principle to get the total number
of 4-digit numbers with first digit equal to 4 or 5.
Counting
7
Decision trees

Trees that provide the number of outcomes of an event based on
a series of possible choices are called decision trees.
Tony is pitching pennies. Each toss results in heads (H) or tails
(T). How many ways can he toss the coin five times without
having two heads in a row?

There are 13 possible outcomes as seen from the tree.

Section 3.2
Counting
8