Transcript 4 countingx

Counting
• Often in CS we need to
– Enumerate/account for all possibilities of something, such
as:
• generating passwords
• exhaustive testing of an algorithm
– Calculate a probability
• In general, there are two ways to count:
– Chicken method  We’ll get an answer eventually, but we
won’t necessarily understand why
– Analytically  but we need to learn some rules
Counting outline
• Some types of problems to address
1. Definition of probability
–
–
Based on some “experiment” or “event” that has a set of
outcomes called our sample space.
P = (# favorable outcomes)/ (total in sample space)
2. Multiplication rule, i.e. fundamental counting principle
–
Number of possible phone numbers or license plate numbers
3. Permutations
4. Combinations
• *** See handout for details
• Common technique required: break a problem down
into distinct cases.
Multiplication rule
• If you need to make consecutive (or independent)
choices, just multiply.
– If you have x ways of making one decision, and y ways of
making a second decision, the total number of outcomes is
xy.
• We can generalize to a “lining up” situation. If you
have x items that need to be arranged in some order,
this can be done in x! ways.
• Sometimes we have different cases to add.
– E.g. At 3:00, you may choose from either the lunch or
dinner menu. Do lunch and dinner separately, then add.
Distinguishable
• The number of ways to line up n objects, but a of
them are identical, b of them are identical, etc.
= n! / (a! b! …)
• Think of 3 people sitting in a row of 3 chairs versus 5
chairs.
• Examples: How many ways can we arrange the
letters in the following words?
– NEEDED
– DIVISIBILITY
– AAABBB
6! / (3! 2!)
12! / 5!
6! / (3! 3!)
Handling restriction
• (This is a permutation problem with a twist.)
• We need to select a president, vice president and
secretary from 10 people. However, A can’t be
president and B cannot be secretary. How many
ways can this be done?
• Focus on cases that are legal:
–
–
–
–
B is president, A is VP, anyone else can by sec’y
B is president, A is secretary, anyone else can be VP
B is VP, A is sec’y, anyone else can be president, etc.
…Is there an easier approach?
Combinations
•
•
•
•
Definition
Contrast with permutations
Evaluating
Applications
• Practice
When to use
• Questions dealing with making some selection,
membership, inclusion, presence vs. absence…. In
which order does not matter
• Combinations answer this type of question: A set
has n elements. How many subsets contain r
elements?
– Try examples when n = 4.
• Contrast with permutations:
– How many ways can we select 3 letters from the alphabet?
– How many 3 letter words can we make?
Points to remember
• Order doesn’t matter
– Subsets, committees
– What matters is whether something is chosen or not.
• Evaluation:
– The number of ways to choose r items out of a set of n is
n! / (r!(n – r)!).
n

– Shorthand notation: C(n, r) or  
r
 
– Shortcut to evaluate: C(10, 3) = 10 * 9 * 8 / (3 * 2 * 1)
– Incidentally: choosing r is the same as (not) choosing n – r.
Examples
• How many 8-bit representations have exactly three
0’s?
– Choose which positions get a 0: choose 3 out of 8: C(8, 3).
• Six people need to be divided into two teams A and
B. How many ways can this be done?
– Choose 3 to go to team A: C(6, 3).
– Choose 3 remaining people for B: C(3, 3) = 1.
• What is the probability that exactly 4 out of 7 coin
tosses will be heads?
– Choose which 4 occurrences are heads: C(7, 4).
– Divide by the total size of sample space: 27.
Watch the wording
•
•
•
•
Sometimes we want “at least” or “at most”
Both
Neither
Be careful with “or”. There could be overlap.
– King or club
– Number or red
• Are objects/categories distinguishable?
– “two teams” may be indistinguishable
– Selecting cards from a deck: almost always the order that
we deal cards does not matter
Indirect probability
• Sometimes it’s easier to find the probability that an
even will NOT happen, and then subtract from 1.
• Ex. Suppose we roll 5 dice, as in Yahtzee.
–
–
–
–
P(all sixes) = 1/7776
P(didn’t get all sixes) = 1 – 1/7776
P(1000 tries, didn’t get all sixes) = (1 – 1/7776)1000
P(1000 tries, got all sixes at least once) = 1 – (1 – 1/7776)1000
• Ex. The “birthday problem.” In a group of n people,
what is the probability that at least two of them have
the same birthday? What is n if p > ½?
Poker hands
• How many straight flushes are there?
– The high card can be anything from 5 up to Ace.
– All cards of the same suit, so select a suit.
• How many 4-of-a-kind hands?
– Choose which denomination you want 4 of.
– Choose those 4 cards.
– Choose the 5th card.
• Full house?
– Choose two denominations.
– Choose three of one and two of the other.
More counting problems
• Indistinguishable subsets
• Ball-in-urn: the objects being selected are identical
• Pascal’s triangle, a combinatorical argument
• Stirling numbers
Indistinguishable subsets
• How many ways can 4 people divide into 2 teams of
2, as in a doubles match?
– The teams are the same size and don’t have inherent
name, place, uniform, etc.
– AB/CD, AC/BD, AD/BC
– Is the answer 3 or 6?
• How many ways to divide … ?
– 20 people into 4 teams of 5
– 20 people into teams of 3, 4, 5, 8
– 20 people into teams of 4, 5, 5, 6
Ball in urn
• The number of ways to distribute
– n distinct objects into r categories = rn
– n identical objects into r categories = C(n + r – 1, n)
• Give 4 cards to 2 people.
– If face up, they are distinct. Each card has 2 possible
destinations  24.
– If face down, then the only thing that matters is how many cards
you have.
Your cards and my cards are separated by a divider
CARD CARD CARD / CARD
0
0
0
1
0
2 categories  1 divider that can go anywhere:
answer = C(5, 1) or C(5, 4).
Ball in urn (2)
• Give 5 cards to 3 people.
– If distinct, ask each card where it’s going: 35.
– If identical:
CARD CARD / CARD CARD / CARD
0
0 1 0
0
1 0
3 categories  2 dividers that can go anywhere
Total = C(7, 2)
• 3 divers find 5 gold coins. How many ways to share?
• A case of 12 bottles of wine to distribute among 4
tables.
Ball in urn (3)
• What if we must give each table at least 1 bottle of
wine?
– We have less freedom to choose.
– Only 8 bottles can be freely distributed.
• Let’s buy 7 cans of soup. 3 varieties are available.
Ride tickets
• Buy 10 ride tickets at the fair. There are 3 possible
rides.
– If the issue is how many times you want to go on each, this
is a ball in urn problem  C(10 + 3 – 1, 2)
– If order matters  310
– If the tickets say we must go in haunted house 4 times,
roller coaster 3 times and ferris wheel 3 times, and order
matters. It’s a combination question. Choose when you
do each type of ride  C(10, 4) * C(6, 3) * C(3, 3).
– If the tickets are bought 4x, 3x and 3x, and order doesn’t
matter  1.
• *** More examples from book and handout.
Understanding C(n, r)
• Let’s justify: C(5, 2) = C(4, 1) + C(4, 2)
• We want to select two elements from { A, B, C, D, E }.
– Is E part of the selection?
– If so, then we pick one of the others: C(4, 1)
– If not, then we pick both from the others: C(4, 2).
• This line of reasoning works in general for C(n, r).
• Now that we understand Pascal’s triangle, let’s look
at another one. 
What good is Pascal’s Δ
• Combinatorical arguments
– C(n, r)  numbers in Pascal’s triangle 
– Stirling numbers
• Recap important ideas
– When to use formulas: n!, P(n, r), C(n, r), C(n + r – 1, n)
– Go over practice handout
Stirling numbers
• S(n, r) = the number of ways to break up a set of n
elements into r groups.
r=1
r=2
r=3
r=4
r=5
n=1
1
n=2
1
1
n=3
1
3
1
n=4
1
7
6
1
n=5
1
15
25
10
1
n=6
1
31
90
65
15
r=6
1
• If you study these numbers in detail, you can solve
more complex counting problems, and determine
coefficients of more Bernoulli-type summations!
Starting simple
• Let’s consider S(3, 2). How many ways can we split
up a 3-element set { A, B, C } into two groups?
Note: their sizes must be 1 and 2.
– A / BC
– B / AC
– C / AB
• Consider S(3, 3). Splitting { A, B, C } into 3 groups.
– A/B/C
• Next, let’s work out various cases of S(5, r)
for 1  r  5.
S(5, r)
• S(5, 1): We need to “split up” a set of 5 elements
into a single group. Degenerate case: we want 1
group of size 5. Answer = 1.
• S(5, 2): Split into 2 groups
– Their sizes could be 2 and 3. In this case, we have groups
like A B / C D E. Select which 2 go in one group: C(5, 2).
– Their sizes could be 1 and 4. In this case, we have groups
like A / B C D E. Select 1 to go into the first group: C(5, 1).
– Answer is the sum: 10 + 5 = 15.
S(5, r) continued
• S(5, 3): We need to split into 3 groups
– The sizes could be 1, 1, 3. For example A / B / CDE. Think of
it in terms of distinguishable permutations. The 5 elements
can be ordered in 5! ways. But the 3 elements in the size-3
group have no inherent order, so we have to divide by 3!.
Also, the two groups of size 1 are indistinguishable, so we
divide by another 2!. 5!/(3!2!) = 10
– The sizes could be 1, 2, 2. For example A / BC / DE. The
total number of permutations is 5!. But the 2 groups of 2
are indistinguishable. Also, the pairs of values inside each
group of 2 are indistinguishable. 5!/(2!2!2!) = 15.
– Total = 25.
S(5, r) continued
• S(5, 4): We need to split into 4 groups
– The sizes could only be 1, 1, 1, 2. The two positions inside
the size-2 group are not distinguishable, and the 3 groups of
size 1 are not distinguishable. 5!/(2!3!) = 10.
• S(5, 5): pulverize the set of 5 into singleton sets. Just
one way to do it. (You can think of all 5 size-1 groups
as being indistinguishable, and 5!/5! = 1)
• So, row 5 of Stirling’s triangle is: 1, 15, 25, 10, 1
General approach
• It’s a bit tedious to keep evaluating each S(n, r) from
scratch in terms of every possible case of group size.
• Let’s make use of earlier/lower values of S.
• Consider S(6, 3). Split { A, B, C, D, E, F } into 3 parts.
• When we partition into groups, we may have F by
itself.
– F / (2 more groups of A-E). Answer = S(5, 2).
– After partitioning A-E, just put F into any current group.
There are 3 to choose from. Answer = 3 * S(5, 3)
– Add it up: S(5, 2) + 3 * S(5, 3)
– In general: S(n, r) = S(n – 1, r – 1) + r * S(n – 1, r)
Using the formula
• How can we use the Stirling formula to quickly
determine S(n, r) for higher values of n?
• Cell value = NW + N * (column number)
– Observe 90 = 15 + 25*3 and 65 = 25 + 10*4
r=1
r=2
r=3
r=4
r=5
n=1
1
n=2
1
1
n=3
1
3
1
n=4
1
7
6
1
n=5
1
15
25
10
1
n=6
1
31
90
65
15
r=6
1