Transcript Slide 8 - counting - Computer Science Department

Chapter 6, Counting and Probability
CMSC 250
1
Counting

Counting elements in a list:
– how many integers in the list from 1 to 10?
– how many integers in the list from m to n? (assuming m <= n)
CMSC 250
2
How many in a list divisible by something

How many positive three-digit integers are there?
– (this means only the ones that require 3 digits)
– 999 – 100 + 1 = 900

How many three-digit integers are divisible by 5?
– think about the definition of divisible by
x | y  ( k Z)[y = kx] then count the k’s that work
100, 101, 102, 103, 104, 105, 106,…,994, 995, 996, 997, 998, 999
20  5
21  5
…
199  5
– count the integers between 20 and 199
– 199 – 20 + 1 = 180
CMSC 250
3
Probability




The likelihood of a specific event.
Sample space = set of all possible outcomes
Event = subset of sample space
Equal probability formula:
– given a finite sample space S where all outcomes are equally
likely
– select an event E from the sample space S
– the probability of event E from sample space S:
n( E )
P( E ) 
n( S )
CMSC 250
4
Coins and cards and dice

Two coins
– sample space = {(H,H), (H,T), (T,H), (T,T)}

Cards
– values: 2,3,4,5,6,7,8,9,10,J,Q,K,A
– suits: D(), H(), S(), C()

Dice
– sample space
{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),
(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),
…
(6,1),(6,2),(6,3),(6,4),(6,5),(6,6)}
CMSC 250
5
Multi-level probability


If a coin is tossed once, the probability of head = ½
If it’s tossed 5 times
1 1 1 1 1
1
*
*
*
*

– the probability of all heads:
2 2 2 2 2 25
5
– the probability of exactly 4 heads:

25
This is because the coin tosses are all independent
events
CMSC 250
6
The breakfast problem



CMSC 250
Suppose your cereal can be Rice Krispies,
cornflakes, Raisin Bran, or Cheerios.
Suppose your drink can be coffee, orange juice, or
milk.
How many ways can you have breakfast?
7
The multiplication rule

If the 1st step of an operation can be performed n1 ways
And the 2nd step can be performed n2 ways
…
And the kth step can be performed nk ways
Then the operation can be performed n1n2  ∙ ∙ ∙  nk ways

Cartesian product n(A)=3, n(B)=2, n(C)=4




– n(A  B  C) = 24
– n(A  B) = 6
– n((A  B)  C) = 24
CMSC 250
8
Discrete Structures
CMSC 250
Lecture 34
April 21, 2008
CMSC 250
9
Using the multiplication rule for selecting
a PIN

Number of 4 digit PINs of (0,1,2,.)
– with repetition allowed = 4  4  4  4 = 256
– with no repetition allowed = 4  3  2  1 = 24

Extra rules :
– . (the period) can’t be first or last
– 0 can’t be first
• with repetition allowed = 2  4  4  3
• without repetition allowed = 2  2  2  1
CMSC 250
10
Probabilities with PINs

Number of 4 digit PINs of {0,1,2,.}
– with repetition allowed = 4  4  4  4 = 256
– with no repetition allowed = 4  3  2  1 = 24



What is the probability that your 4 digit PIN has no
repeated digits?
What is the probability that your 4 digit PIN does have
repeated digits?
Probability of the complement of an event
P(E’) = P(Ec) = 1  P(E)
CMSC 250
11
The difference rule formally

If A is a finite set and B  A, then
n(A B) = n(A) – n(B)

One application: probability of the complement of an
event:
P(E’) = P(Ec) = 1  P(E)
CMSC 250
12
PINs with less specified lengthaddition rule


Assume a PIN can be of length 2, 3, or 4, using {0,1,2,.}
Partition the problem:
– number of length-2 PINs w/rep allowed: 4  4 = 16
– number of length-3 PINs w/rep allowed: 4  4  4 = 64
– number of length-4 PINs w/rep allowed: 4  4  4  4 = 256

Number of PINs if allowing length 2, 3, or 4 = 336
CMSC 250
13
The addition rule formally


If A1  A2  A3 …  Ak = A
and A1, A2 , A3,…,Ak are pairwise disjoint
in other words, if these subsets form a partition of A, then
n(A) = n(A1) + n(A2) + n(A3) + ∙∙∙ + n(Ak)
CMSC 250
14
The inclusion/exclusion rule

If there are two sets:
n(A  B) = n(A) + n(B)
– n(A  B)

If there are three sets:
n(A  B  C) =
n(A) + n(B) + n(C)
– n(A  B) – n(A  C) – n(B  C)
+ n(A  B  C)
CMSC 250
15
Discrete Structures
CMSC 250
Lecture 35
April 23, 2008
CMSC 250
16
Permutations

Different ways of arranging all n of n objects
– in either a line or a circle
– without duplication/all items distinguishable
– note: order is taken into account

Number of linear permutations of N objects = N!
N possible for 1st position  (N – 1) for 2nd  ∙ ∙ ∙  1 for last

Number of circular permutations of N objects = (N  1)!
Fix one person,
then (N – 1) possible for next position * (N – 2) for 2nd  ∙ ∙ ∙  1 for
last
CMSC 250
17
r-permutations

If there are n things in a set, and you want to line up
only r of them
n!
P(n, r )  n P r 
(n  r )!

Example:
Class = {Alice, Bob, Carol, Dan}
– select a president and a vice president to represent the class
– select a president, vice president, and webmaster
CMSC 250
18
Combinations

Different ways of selecting objects
– counting subsets
– without duplication/all items distinguishable
– note: order is not taken into account
0
(n, r  Z where n  r )

C (n, r ) 


n
r

P(n, r )
n!


r!
(n  r )!r!
Examples: suppose {Alice, Bob, Carol, Dan} are on the
ballot
– select two superdelegates
– select three superdelegates
CMSC 250
19
Permutations but of indistinguishable items

Examples:
– Arrangements of the word “baboons”
– Assume you have a set of 15 beads:
• 6 green
• 4 orange
• 3 red
• 2 black
select positions of the green ones, then the orange ones, then the
red ones, then the black ones (or a different order of selecting their
positions would work as well)

15
6
CMSC 250
15!
*  *  *    6!4!3!2!
9
4
5
3
2
2
20
Discrete Structures
CMSC 250
Lecture 36
April 25, 2008
CMSC 250
21
Combinations with repetition




{a,b,c,d,e}
How many 3-combinations can be made without
repetition?
How many 3-combinations can be made with unlimited
repetition allowed?
These are multisets [a,b,c]
– not sets {a,b,c}
– and not tuples (a,b,c)

How many combinations of 20 a's, b's, and c's can e
made with unlimited repetition allowed?
CMSC 250
22
Notice similarities

The number of nonnegative integer solutions of the
equation
x1  x2      xn  r
xi  0, i  Z
1i  n

The number of selections, with repetition, of size r from a
collection of size n.

The number of ways r identical objects can be distributed
among n distinct containers.
CMSC 250
23
Choosing r elements out of n elements
order doesn’t matter
order matters
repetition
allowed
repetition not
allowed
CMSC 250
n


n  n

r times
r
 n  r  1


r


n!
n


n!
P(n, r ) 
 
(n  r )!  r  (n  r )!r!
 
24
Probability with combinations

Assume:
– there are 32 people in a class
– seven will be chosen to get extra homework

What is the probability that you get extra homework?

Number of ways to select the lucky seven
Number of ways to select if you get homework
P(you get homework)


CMSC 250
25
Tournament play


Team A and Team B compete in a “best of 3” tournament
They each have an equal likelihood of winning each game
–
–
–
–
CMSC 250
Do the leaves add up to 1?
Do they always have to play 3 games?
What's the probability the tournament finishes in 2 games?
Do A and B have an equal chance of winning?
26
What if A wins 2 of every 3 games?


Each line for A must have a 2/3
Each line for B must have a 1/3
– How likely is A to win the tournament?
– How likely is B to win the tournament?
– What is the probability the tournament finishes in two
games?
CMSC 250
27
Where the multiplication rule doesn’t work


People= {Alice, Bob, Carolyn, Dan}
Need to be appointed as president, vice-president, and
treasurer, and nobody can hold more than one office
– how many ways can it be done with no restrictions?
– how many ways can it be done if Alice doesn’t want to be
president?
– how many ways can it be done if Alice doesn’t want to be
president, and only Bob and Dan are willing to be vicepresident?
CMSC 250
28
Discrete Structures
CMSC 250
Lecture 37
April 28, 2008
CMSC 250
29
Harder examples of selecting representatives

1.
2.
3.
4.
5.
CMSC 250
Candidates= {Azar, Barack, Clinton, Dan, Erin, Fred}
select two, with no restrictions
select two, assuming that Azar and Dan must stay
together
select three, with no restrictions
select three, assuming that Azar and Dan must stay
together
select three, assuming that Barack and Clinton
refuse to serve together
30
Properties of combinations and their
proofs

n
2
  1
  n
n
0
n
1
n( n  1)

2

 
n
n 1
n
n 1 
 
n
n2
n
n( n  1)

2
   
n
r
CMSC 250
n
nr
31
The binomial theorem
( x  y)  x  y
( x  y)2  ( x  y)(x  y)  x 2  xy  xy  y 2  x 2  2xy  y 2
( x  y)3  ( x  y) 2 ( x  y)  ( x 2  2 xy  y 2 )(x  y) 
x 3  2 x 2 y  xy 2  x 2 y  2 xy 2  y 3  x 3  3x 2 y  3xy 2  y 3
( x  y ) 4  ( x  y )3 ( x  y )  ( x 3  3x 2 y  3xy 2  y 3 )(x  y ) 
x 4  3x 3 y  3x 2 y 2  xy3  x 3 y  3x 2 y 2  3xy3  y 4 
x 4  4 x 3 y  6 x 2 y 2  4 xy3  y 4
 4 4  4 3
 4 2 2  4 3  4 4
( x  y)    x    x y    x y    xy    y
 0
1
 2
 3
 4
n
 n  i n i
n
( x  y)    x y
i 0  i 
CMSC 250
4
32