Transcript Combinatorics

Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Combinatorics
Introduction
– Combinatorics is the study of the arrangement
of discrete objects
– Who Cares?
• Counting is important whenever we have finite
resources
• Examples:
–
–
–
–
Words of memory needed to store …
Instructions needed to solve …
Number of hits per second supported by …
A password must be between six and eight
characters long. The characters can be a digit or a
letter (case sensitive). Each password must include
at least one digit. How many passwords can we
support?
Useful Counting Cheat Sheet
– Summation Notation
– Summation Properties
– Summation Formulas
Basic Counting Principles
– Multiplication Principle
If there are n1 possible outcomes for a first event and n2 possible
outcomes for a second even, then there are n1  n2 possible
outcomes for the sequence of the two events.
• Extends (by induction) to apply to a sequence of n events
– Examples
1.
2.
3.
How many different bit strings are there of length seven?
If A & B are finites sets, then |A  B| = _______.
How many possible 7 digit phone numbers are there?
• What if you can’t use a digit more than once?
Basic Counting Principles
– Addition Principle
If A and B are disjoint events with n1 and n2 possible outcomes,
then the total number of possible outcomes for event “A or B” is
n1 + n2.
• Extends (by induction) to n disjoint events
– Examples
1.
2.
3.
How many ways are there to elect an ACM president if the
president must be a CS faculty member (from 7) or a CS
major (from 250)?
If you have two disjoint sets, A & B, |A  B| =_________.
How many 7 digit phone numbers begin with 441 or 781?
Basic Counting Principles
Practice Example
US Social Security Numbers are 9 digits (0..9)
1. How many Social Security numbers are there?
2. How many are even?
3. How many have all even digits?
4. How many are palindromes?
5. How many have none of their digits equal to 8?
6. How many have at least one digit equal to 8?
7. How many have exactly one 8?
Basic Counting Principles
– Inclusion-Exclusion Principle
If you have two arbitrary sets, A & B,
|A  B| = |A| + |B| - |A  B|
• Example: How many bit strings of length eight start with a 1
or end with the two bits 00?
–
Answer: 27 + 26 – 25 = 160
• Subsumes the Sum Rule
• Extends (by induction) to n arbitrary sets (see p. 228 of text)
A
A–B
B
AB
B–A
Example: Internet Address (IPv4)
• Sample: 137.28.109.33
• Translation: 32-bits
10001001 00011100 01101101 00100001
• Interpretation
Plus some
additional
classes
• Restrictions
– 1111111 not available as netid of Class A network
– All 0s or all 1s are not allowed as any hostid
• How many possible computer Internet addresses?
– Netid for Class A is 7 bits long,
– Netid for Class B is 14 bits long,
– Netid for Class C is 21 bits long
Example: Internet Address
How many possible computer Internet addresses?
Class A: ((27 – 1) * (224 – 2)) +
1111111 prohibited as netid
Class B: (214 * (216 – 2)) +
all 0’s and all 1’s prohibited
Class C: (221 * (28 – 2))
= 3,737,091,842.
Permutations
– An ordered arrangement of n elements from a set
– An r-permutation is an ordered arrangement of r
elements taken from a set of n elements
– The number of r-permutations of n items P(n,r)
P(n,r) = n! / (n – r)!
– Examples:
1.
2.
How many ways are there to select a 1st, 2nd, and 3rd place
winner from 100 different people?
How many 7 digit phone numbers exist where the numbers
can’t be repeated?
– Notice:
• P(n,n) = n!
• P(n,0) = 1
• P(n,1) = n
Combinations
– An unordered arrangement of n elements from a set
• unordered means order does not matter!
– An r-combination is an unordered arrangement of r
elements taken from a set of n elements
– The number of r-combinations of n items C(n,r)
C(n,r) = n! / r!(n – r)! = P(n,r) / r!
– Examples:
1.
2.
Quality Control wants to test 25 microprocessor chips from
the 300 manufacturers. In how many ways can this be done?
How many ways can I select 5 different fruits from choice of
10?
– Notice:
• C(n,n) = 1
• C(n,1) = n
• C(n,0) = 1
• C(n,r) = C(n,n-r)
Repetition
– Thus far we have assumed that items can not be used
twice in one draw
– What if they can?
• Letters in a password
• Selecting from bag of items with copies
– Permutations with repetition
• PR(n,r) = nr
• How many 7 digit phone numbers are possible?
– Combinations with repetition
• CR(n,r) = C(r+n–1, r) = (r+n-1)! / [r!  (n-1)!]
• How many ways can I select 7 pieces of fruit from a selection
of apples, oranges, and pears?
Repetition
– How many different strings can be made by reordering
the letters of the word …
– “FAILURE”?
– “SUCCESS”?
We have three Ss, two Cs, one U, and one E.
Notice that the three Ss can be placed into the seven positions in C(7,3) ways,
leaving four blank positions
The Cs can be placed into those four positions C(4,2) ways, leaving two free
positions.
The U can be placed into those two positions in C(2,1) ways, leaving one free
position (allowing E to be placed in C(1,1) ways).
From the product rule: C(7,3) * C(4,2) * C(2,1) * C(1,1) which equals
(7! * 4! * 2! * 1!) / (3! * 4! * 2! * 2! * 1! * 1! * 1! * 0!) which equals
7! / (3! * 2! * 1! * 1!) which equals 420
Repetition
– Permutations with indistinguishable objects
• PI(n,n1,n2,…,nk) = n! / (n1!  n2!  …  nk!)
Repetition
– Example: How many ways are there to build four hands of 5 cards
from the standard deck of 52 cards?
•
Solution I: Combinations of Objects
– Use Combinations for each player’s hand
– Use Product Rule for total
C(52,5) * C(47,5) * C(42,5) * C(37,5) = 52! / (5!5!5!5!32!)
•
Solution II: Permutations of Indistinguishable Objects
–
5 indistinguishable objects of each of four types (one for each
hand)
– 32 indistinguishable objects of a fifth type (undealt)
52!/(5!5!5!5!32!)
Probability
– An area of mathematics that has its origin in
counting
• Developed to study gambling games
– circa 1650 by Pascal
– generalized circa 1812 by Laplace
– Finite Probability
• experiment – a procedure that yields one of a given
finite set of possible outcomes
• sample space – the finite set of possible outcomes
• event – a subset of the sample space
The probability of an event E, which is a subset of a
finite sample space S of equally likely outcomes, is
p(E) = |E| / |S|
Probability Examples
– What is the probability of picking a winning
combination of six numbers out of 40 (no repeats)?
•
•
•
•

S : set of all six-number sequences taken from 40
E : the target number
|S| = C(40,6) = 3,838,380
|E| = 1
p(E) = 1/3,838,380 (approx. 0.00000026)
– What is the probability that a hand of five cards in
poker contains four of a kind?
•
•
•
•
S : set of all possible poker hands
product rule
E : set of all possible four-of-a-kind hands
|S| = C(52,5) = 2,598,960
|E| = # of ways to pick rank * # of ways to pick other card
= C(13,1) * C(48,1) = 624
 p(E) = 624 / 2,598,960 (approx. 0.00024)
Probability
– Properties
•
•
•
•
•
Each outcome “equally likely” implies
p(a) = 1/n where a  S and |S| = n.
Called uniform distribution
0  p(E)  1
p(S) = 1
p(a)  1

aS
p(E) = 1 – p(E)
p(E1  E2) = p(E1) + p(E2) – p(E1  E2)
– disjoint events
» p(E1  E2) = 0
» p(E1  E2) = p(E1) + p(E2)
• p(E2 | E1) = p(E1  E2) / p(E1)
– independent events
Conditional Probability » p(E |E ) = p(E )
2
1
2
» p(E1  E2) = p(E1)  p(E2)
Probability Practice
1. What is the probability of drawing either an ace
or a spade from a standard deck of cards?
2. What is the probability of drawing 2 aces in a
row?
3. What is the probability of drawing 2 aces in a
row (with replacement)?
Expected Value
First an example
• Find the average height of four students with
heights 68, 72, 67, and 74 inches.
Avg height = (68+72+67+74)/4 = 70.25 inches
• Find the average height of 1000 students with the
following heights
Number Height in
of Students Inches
Avg height =
200
66
66(.2)+68(.25)+71(.3)+72(.1)
250
68
+74(.15) = 69.8 inches
300
71
100
72
150
74
Expected Value
Definitions
• Suppose we have a probability space with the
sample space
{e1, e2, …, en}
• A random variable f (ei) on the sample space is a
real number associated with each outcome ei
• The expected value (or average) of f (ei) is given
by
f (e1 ) p(e1 )  f (e2 ) p(e2 )  ...  f (en ) p(en )
Expected Value
Example
• Suppose we have an asymmetrical 6-side die:
p(1) = 0.2
p(2) = 0.15
p(3) = 0.1
p(4) = 0.25
p(5) = 0.12
p(6) = 0.18
1. A random variable on this sample space is the number
written on the side
The expected value of this random variable is
1(.2) + 2(.15) + 3(.1) + 4(.25) + 5(.12) + 6(.18) =
3.48
2. A random variable on this sample space is the mod 2
function of the number on the side.
The expected value of this random variable is
1(.2) + 0(.15) + 1(.1) + 0(.25) + 1(.12) + 0(.18) =
.42
Application: Monte Carlo Techniques
– Deterministic algorithms don’t always exist or
aren’t always practical
– Use random sampling to compute results
– Example: Value of 
• Let P = set of randomly selected points
–
(x,y) | 0  x  1  0  y  1
• Let S = { (x,y) | (x,y)  P 
• Let a = | S | / | P |
•   4a
x2  y2
 1
}
Application: Monte Carlo Techniques
– Example: Efficiency of backtracking algs
• Generate a “typical” path in the tree using random choices,
then estimate the number of nodes in the tree based on this
path.
• Let m0 be the number of feasible children of the root
• Randomly generate a feasible node at level 1. Let m1 be
the number of feasible children of this node.
• Randomly generate a feasible node at level 2. Let m2 be
the number of feasible children of this node.
...
• Randomly generate a feasible node at level i. Let mi be
the number of feasible children of this node.
...
• Estimate of total number nodes checked:
1 + t0 + m0t1 + m0m1t2 + … + m0m1 … mi-1ti + …
Application: Monte Carlo Estimate
int MonteCarloEstimate( ) {
Node v = root of state space tree;
while(v has children and is not a solution) {
count number of children of v
add number of children into total count using
1 + t0 + m0t1 + m0m1t2 + … + m0m1 … mi-1ti + …
store number of feasible children of v
v = randomly selected feasible child of v
}
return total count
}
Practice Problems
– Section 3.2: 3, 5, 6,12, 52 – 56, 69 - 70
– Section 3.3: 7, 10, 12
– Section 3.4: 4, 5, 11, 12, 20 – 23, 29 – 37, 65
– Section 3.5: 17 – 24, 29 – 38, 44