TREE DIAGRAMS
• Create a tree with a root and a branch for each possible
choice
• Upon completing the tree , the number of leaves will be the
number of possible outcomes
USING TREE DIAGRAMS EXAMPLE #1
• How many nibbles can exsist with no consecutive 1’s ?
First Bit
Second Bit
Third Bit
Fourth Bit
USING TREE DIAGRAMS EXAMPLE #1
• How many nibbles can exsist with no consecutive 1’s ?
1 0 First Bit
Second Bit
Third Bit
Fourth Bit
0000
USING TREE DIAGRAMS EXAMPLE #1
• How many nibbles can exsist with no consecutive 1’s ?
1 0 First Bit
0 1 0 Second Bit
Third Bit
Fourth Bit
USING TREE DIAGRAMS EXAMPLE #1
• How many nibbles can exsist with no consecutive 1’s ?
1 0 First Bit
0 1 0 Second Bit
1 0 0 1 0 Third Bit
Fourth Bit
USING TREE DIAGRAMS EXAMPLE #1
• How many nibbles can exsist with no consecutive 1’s ?
1 0 First Bit
0 1 0 Second Bit
1 0 0 1 0 Third Bit
0 1 0 1 0 0 1 0 Fourth Bit
USING TREE DIAGRAMS EXAMPLE #1
• How many nibbles can exsist with no consecutive 1’s ?
1 0 First Bit
0 1 0 Second Bit
1 0 0 1 0 Third Bit
0 1 0 1 0 0 1 0 Fourth Bit
1010 1001 1000 0101 0100 0010 0001 0000
USING TREE DIAGRAMS EXAMPLE # 2
A playoff between two teams consists of at most five games.
The first team that wins three games wins the playoffs. How
many different ways can the playoffs occur?
USING TREE DIAGRAMS EXAMPLE # 2
USING TREE DIAGRAMS EXAMPLE #3
At Stone Cold Magic, we sell our “ I ❤️Magic” Tshirts in 5 different
sizes:
1. Large (L)
2. Extra Large (XL)
3. Bigger (B)
4. Ginormous ( G)
5. Freakin’ HUGE (F)
USING TREE DIAGRAMS EXAMPLE #3
Each shirt comes in four colors:
Black (B)
Light Black (LB)
Dark Black (DL)
Really Dark Black (RDB)
Ginormous only comes ing Light black, dark black and really dark black
1. Freakin HUGE only comes in Dark black and Really dark black
Using a Tree Diagram show how many different unique T-Shirts exist.
USING TREE DIAGRAMS EXAMPLE #3
F
L XL B G
L D RD L D RD
B B B
B
B B B
B D RD
B B
B L D RDB L D RD
B B B B B
PIGEON HOLE PRINCIPLE
Defined :
• There are at least 2 objects in one box whem there are
more objects than boxes
PIGEON HOLE PRINCIPLE
Defined :
• There are at least 2 objects in one box whem there are
more objects than boxes
PIGEON HOLE PRINCIPLES EXAMPLES
• How many people need to be in room to guarantee that at
least 2 of them have the same birthday?
• How many students need ro exist in a classroom to
guarantee that you will find at least two students with
exact same number of points on a 100 point exam?
• How many words are needed to guarantee that at least 2 of
them start wirh the same letter of the alphabet?
PIGEON HOLE PRINCIPLES EXAMPLES
• How many people need to be in room to guarantee that at
least 2 of them have the same birthday? 367
• How many students need ro exist in a classroom to
guarantee that you will find at least two students with
exact same number of points on a 100 point exam? 102
• How many words are needed to guarantee that at least 2 of
them start wirh the same letter of the alphabet? 27
PIGEON HOLE PRINCIPLE GENERALIZED
• If there are N objects placed into K boxes, the there is at
least on one box containing at least [N/K] number of
objects.
PIGEON HOLE PRINCIPLE
If there are N objects placed into K boxes, the there is at
least on one box containing at least [N/K] number of objects.
N=7
K=6
[N/K]=2
PIGEON HOLE PRINCIPLE GENERALIZED
• If there are N objects placed into K boxes, then there is at
least one box comtaining at least number of objects
• Among any set of 21 decimal digits, there must be 3 that
are the same.
• 124920703481081028391
PIGEON HOLE PRINCIPLE GENERALIZED
• If there are N objects placed into K boxes, then there is at least one
box comtaining at least number of objects
• Among any set of 21 decimal digits, there must be 3 that are the
same.
• 1234567890
• 1234567890 N=21
• No matter what the 21st number is, it will be a triplicate. K=10
• What are the pigeons, and what are the holes? [N/K]=3
WHY DO WE CARE ABOUT COUNTING?
WHY DO WE CARE ABOUT COUNTING?
What is the probability that I’ll roll a 1 on a normal
unweighted six-sided die?
WHY DO WE CARE COUNTING?
What is the probability that I’ll roll a 1 on normal unweighted six-sided
die? 16.7%
How do we know?
F.O
P.O
With dice it’s easy , but sometimes knowing what the numerator and
denominator is can be very tricky.
What’s the probability of getting a full house in a game of 5 card poker?
WHY DO WE CARE ABOUT COUNTING?
What’s the probability of getting a full house in a game of 5 card
poker?
F.O
P.O
F.O = FULL HOUSE
P.O = # OF 5 CARD HANDS POSSIBLE
Solving this requires counting techniques we’ve learned, and more that
we’ve yet to learn (i.e., permutations and combinations).
WHY DO WE CARE ABOUT COUNTING?
1. Discrete probability is the foundation of Bayes’ Theorem
and Bayesian statistics.
2. Bayes’ Formula is used in computer science (for example
in Spam filters) and elsewhere.
3. To understand Bayes’s Theorem, we need to understand
probability.
4. To understand and calculate probability, we need to know
proper counting techniques.
QUESTIONS????
