Transcript Counting Principles

Counting Principles
I. Basic Counting Problem
 Say that I have a jar with 7 balls in it numbered
1 through 7. How many ways can 10 be made
(by addition of the numbers on the balls) if I
pull a ball out of the jar, put it back, and then
draw out a second ball.
II. Fundamental Principle
of Counting
 Definition: Let A and B be two events.
Say event A can occur in m different
ways. After A has occurred, say event B
can occur in n different ways. Then the
number of ways that the two events can
occur is m·n.
II. Fundamental Principle
of Counting



EXAMPLE:
You want to redesign your Facebook
profile and change the layout to see only 3
applications. You want one application that
pertains to your friends, one that pertains
to music, and one that pertains to
pictures/videos.
If these are the applications you have
available in each category, how many
layouts are possible:
 Music: 1. iLike
2. My Band
3. Profile Song
 Friends: 1. Top Friends
2. Compare Friends
 Pictures/Videos: 1. My Flickr
2. Slideshows
3. Graffiti
4. Animoto Videos
 Answer: 3x2x4=24
II. Fundamental Principle
of Counting
 EXAMPLE:
 Your little brother just broke into your Facebook account and now
you need to change your password. You want it to be 5 characters
long. The first 3 characters are to be letters and the last 2
characters are to be numbers. How many passwords are
possible? What if you don’t want to repeat letters and numbers?
 Answer: 26x26x26x10x10=1,757,600
 Answer: 26x25x24x10x9=1,404,000
II. Fundamental Principle
of Counting
 EXAMPLE:
 Say that you have 42
friends on Facebook. Any
time you access your
profile, 6 of your friends
will appear in a box below
your picture. Each time
these friends are
randomly generated out of
your 42 friends. How
many different
arrangements of 6 people
can show up?
 Answer:
 42x41x40x39x38x37=
3,776,965,920
Just to note…
 This can also be thought of as: n
Pr
 Permutations of n objects taken r at a time.
 For this example we would have 42P6
which would get you the same answer
II. Fundamental Principle
of Counting
 EXAMPLE: (like #15,19 on HW)
 What if your friend Ally or
boyfriend Bobby must be
in position one, that is,
they are your only 2
choices for that first spot?
(note: you still have 42
friends)
 Answer:
 2x41x40x39x38x37=
179,855,520
III. Permutations
 Aka: Arranged in order
 This is determining the number of ways n
elements can be arranged in order.
 Definition of Permutation: An ordering of
n different elements such that one
element if 1st, one is 2nd, one is 3rd and so
on.
III. Permutations
 EXAMPLE: You want to upload these 6 pictures on
Facebook. How many permutations are possible for the
6 pictures?
 Answer: 6x5x4x3x2x1=6!=720
III. Permutations
 So….. the number of permutations of n
elements is given by:
n·(n-1)……4·3·2·1=n!
III. Permutations
 EXAMPLE:
You want to upload these 6 pictures on Facebook, but this time you want
the two dog pictures have to be next to each other, the two cat pictures have to be next to each
other, and the two scenic pictures have to be next to each other? How many permutations are
possible for the 6 pictures?
 Answer: 3!x2x2x2=48
IV. Distinguishable
Permutations
BANANA
ABNANA
(if I switch 1st and 2nd letters)
What happens if I now switch the first and last letters of
ABNANA?
IV. Distinguishable
Permutations
 The number of distinguishable permutations of n objects is:
 Where n1, n2, …, nk are the amounts of the numbers or letters that
are repeated.
 For BANANA we have 6!/(3!2!)=60 distinct permutations, because
we have 2 N’s and 3 A’s in BANANA and 6 letter total.
IV. Distinguishable
Permutations
 EXAMPLE: So your mom just got
Facebook…not cool! You want to
disguise your name by scrambling up the
letters in you first and last name so she
can’t find you. If your name is, Hannah
Christopherson, how many new first and
last names can you make with the
letters?
 Hannah: 6!/(2!2!2!)=90
 Christopherson:
14!/(2!2!2!2!)=5,448,643,2000
V. Combinations
 Order is not important (permutations it is)
{A, B, C} v. {B, A, C} you would only choose
one since both have the same three letters.
 Combinations of n elements taken r at a
time is:
nCr=n!/(n-r)!r!
 So you are collecting subsets of a larger
set
V. Combinations
 EXAMPLE:
You are having a party
this weekend and you
want to invite 25 of
your 30 Facebook
friends. How many
groups of 25 can you
choose from your 30
friends?
 Answer
30C25=142,506
Counting in our life…
 Cards
 Number of possible poker
hands….
 Combination Locks
 Where order matters?
 Say you have a 39 number
 Where order doesn’t
combination lock on your
matter?
bike. What is the probability
 Can use counting to find
someone could steal your
the probability of a certain
bike by figuring out your
poker hand, like a full
code?
house or a flush.
License plates, zip codes, phone numbers, etc…..
Say a zip code must fit this criteria:
1st digit: 2-9
3rd digit: 0-9
2nd digit: 0-9
4th digit: 4-9
5th digit: 1-8