These notes are intended to supplement the textbook and lectures in CS 237 in order to help you analyze and solve problems throughout the course. This part of the course is essentially developing a "toolbox" of counting techniques for the typical problems that arise in classical probability. Becoming familiar with the tools, and knowing which tool applies to which problem, is essential. In addition, I provide some guidance on translating various common phrases in English into mathematical language.
This is a work in progress, and I welcome comments and additions to the list of ideas!
We have
(a) There is a Population of N elements that are used to create an outcome.
The important points to notice about the basis collection are:
- Its cardinality, in particular, it is infinite?
- Are objects distinguishable or indistinguishable (i.e., are different objects but look identical to other objects)?
Examples: number of dots showing on a rolled die; letters in the alphabet, people in a group, playing cards in a standard 52 deck, balls of various colors in a sack.
(b) K elements are selected from this collection to construct an outcome.
Examples: Roll a die twice, or row 2 dice and observe the dots showing on the face; select 5 letters, select two balls from the sack, deal a 5-card hand from the deck.
(c) The elements are used to construct an outcome, generally
- a sequence (a collection with an ordering, with possible duplicates),
- a set (an unordered collection without duplicates),
- or a bag or multiset (an unordered collection with possible duplicates).
Example: Collect 5 selected cards into a poker hand; arrange the 5 letters to make a word.
The important issues to note are (and you probably want to figure them out in this order):
(i) Is the outcome ordered or unordered? Does the outcome have duplicates or not?
Examples: If the two numbers showing on the dice are 2 and 5, put them in sequence: [2,5] or in a set { 2,5 }; put the 5 letters into a sequence (a word) in which the order matters; put the 5 cards into a hand in which order does not matter (it is a set).
Note: in the case of [2,5] you may speak of the "first roll" or the "second roll" but in { 2,5 } you may only make statements about the collection without specifying an order ("at least one of the rolls is 5"). Words are sequences, and hands in card games are sets; otherwise you need to use context or it will be clear from the problem statement.
(ii) Is the selection done with or without replacement?
Examples: Selecting 5 cards for a poker hand is done without replacement (you keep the cards and don't put them back in the deck); choosing a committee of 3 from a group of 10 people is without replacement; in many cases, as with balls in a sack, it is part of the problem statement.
(iii) Does the basis collection have duplicates or not?
Examples: The collection of letters in "MISSISSIPPI" has duplicates, but in "WORD" there are no duplicates; two red balls in a sack are indistinguishable by color.
Basic Problem Patterns, Standard Problems and What Formula to Use
If you memorize standard problems for each of the techniques, then you can try to match your new problem to one of them. Often, transforming a problem by changing perspective (e.g., not what passengers get off at which floors, but what floors receive what passengers) allows you to match the problem to a standard problem.
Notes: Problems with duplicates are given in blue, otherwise, we have four possibilities:
Selection Without Replacement Selection With Replacement Ordered Outcome
(Sequence or String)
Standard Problem 1(a): How many permutations of all N letters ABC... (all different)? (If the problem simply says "permutations" this is what they mean.)
Formula: P(N,N) = N!
Example: How many permutations of the word "COMPUTER"? 8!
Standard Problem 1(b): How many permutations of all N letters ABC... where some letters are repeated with multiplicities m1, m2, ..., mp?
Formula: N! / ( m1!* ...• mp!.)
Example: How many different-looking permutations can be made of the word "STATISTICS" = 10! / ( 3! * 3! * 2! )
Standard Problem 2: How many permutations of K letters from N letters ABC... ?
Formula: P(N,K) = N*(N-1)*(N-2)* ... *(N-K+1) = N! / (N-K)!
Example: How many 3-letter words can be made from letters in "COMPUTER"? P(8,3)
Standard Problem: How many enumerations of K letters from N letters ABC....?
Formula: NK
Example: How many 10-letter words all in lower case? 2610
Unordered Outcome
(Set or Multiset)
Standard Problem 1(a): How many combinations (sets) are there of size K from N objects... (all different)?
Formula: C(N,K) = N! / ( (N-K)! * K! )
Example: How many committees of 3 people can be chosen from 8 people? C(8,3)
Standard Problem: How many ways to choose a multiset of K objects from a set of N objects, with replacement?
Formula: C(N+K-1,K)
Example: At your favorite takeout place, there are 10 accompaniments, and you can choose any 3, with duplicates allowed (e.g., you can choose two servings of fries and one of mac and cheese). How many possibilities are there? C(10+3-1,3) = C(12,3) = 220
Miscellaneous Paradigms
Mixed permutations and combinations without replacement
Sometimes our outcomes consist of ordered and unordered arrangments; this is the only common example of this paradigm
Standard Problem: Given a set S of size N, and consider partitions of S into sets P1 ... Pq of sizes m1 ... mq. How many such partitions exist? Note that the partitions are labeled and can not be exchanged.
Formula: N! / ( m1!* ...• mq!.)
Explanation: If you line up the partitions left to right, each permutation of the N objects can then be assigned to a partition (first m1 into P1, next m2 into P2, etc.); since each Pi is a set, you have to remove the redundancy due to the unordered nature of sets. This is the same formula for permutations with redundancies.
Example: How many teams of size 5 and 4 can be made from 9 people? 9! / (5!*4!)
Warning: When the partitions are not distinguished (e.g., how many ways to form two teams of K each) then there is a subtle overcounting because you are considering each "way" twice!
Circular Permutations
If the sequence is ordered, but in a circular arrangement, then we are generally interested in how many "ways" of permuting the sequence, where rotations do not change the "way."
Standard Problem: How many ways of seating N people around a table are there?
Formula: N! / N = (N-1)!
Example: How many ways of seating 4 people around a table? 3! = 6.
Power Set (set of all subsets of S)
If the question asks about subsets of size K, then you should think in terms of C(N,K); similarly if some small number of possible K. But if there is a large number of sizes, you may have to think in terms of the power set of all possible events.
Standard Problem: If you have N people, how many different committies of any number of people can be created?
Formula: 2N
Example: How many kinds of pizza can be made from 10 toppings? 210 = 1024.
Basic Techniques and When to Use Them
The various rules for combining probabilities or cardinalities of sets can be thought of various rules for adding, subtracting, multiplying, and dividing probabilities or cardinalities.
(1) Simplify a calculation using the complement: P(Ac) = 1.0 - P(A)
If there are N possibilities and you have to calculate for "at least 1", then calculate for 0 and subtract:
What is the probability of at least 1 head in two tosses of a die? P(at least 1) = 1 - P( 0 ) = 1 - 1/4 = 3/4.
How many sequences of 3 letters (upper or lower) contain at least one upper case? #( any case ) - #(only lower) = 352 - 326
In general, if you have 1, 2, ...., N, and are asked to calculate for K of them for K < N/2, then it is usually less work to do the smaller problem and subtract.
How many subsets of { red, blue, green, black, grey, white, purple, pink} have between 2 and 7 colors? Calculate for 0, 1, and 8 and subtract from the total number: 28- 1 - 8 - 1.
(2) For events A and B, "A or B" or "A ∪ B" indicates that you add the probabilites/sizes; when A and B are disjoint, you can simply add; when they are not, you have to use Inclusion/Exclusion.
If you are dealt a card from a standard 52 card deck, what is the probability it is a Club or a Diamond? P(Club) = P(Diamond) = 1/4, so P(A or B) = 1/2.
The probability that this card is a Club or an Ace is P(Club) + P(Ace) - P(Ace of Clubs) = 1/4 + 1/13 - 1/52.
(3) For events A and B, "A and B" or "A ∩ B" indicates that when A and B are independent (e.g., choice is with replacement, intuitively they are unrelated physically, or P(A|B) = A or P(B|A) = B), you can multiply. You can NOT multiply when they are not independent, and there is no one general technique to solve this.
Generally, "with replacement" implies independence of choices; "without replacement" MAY indicate that the choice is not independent, but may not! Often you can finess the issue by thinking in terms of a sequence, and calculating directly without worry about replacement or not.
When you toss two dice, what is the probability that you get two heads? P(two heads) = P(one head)*P(another head). Obviously physically independent, the die has no memory of the previous toss.
Choose a card from a deck, replace it, and choose another card. What is the probability of two Clubs? P(2 Clubs) = P(first is club) * P(second is Club). Sequence of two cards, probability is same both times.
Choose a card from a deck, don't replace it and choose another card. P(both clubs) = P(first club)*P(second club). But these are different, so you can't say P(one club)*P(one club). You can avoid worrying about it by analyzing the sequence: 13/52 * 12/51.
Choose two cards without replacement. What is the probability that you get no spades and no face cards? Here, although it is without replacement, these events are independent, so you can still multiply: P(no spades) * P(no face cards) = (39/52 * 38/51) * (40/52 * 39/51).
(4) For "without replacement" problems you can sometimes use k-permutations and sometimes combinations. Let us consider three card problems:
(a) How many hands of cards are there? Is it
52*51*50*49*48 = 311875200
or
C(52,5) = 2598960?
I think you probably understand that the first is the number of sequences of 5 cards, and the second is the number of sets of 5 cards, and we can verify by confirming that considering permutations instead of sets should increase the number by a factor of 5!, that is:
2598960 * 5! = 311875200
But when you are calculating probabilities and the event is being created from one uniform subset (e.g., no face cards) then you can use either, because the order does not really matter (the cards are indistinguishable from the point of view of how they function in the event). Thus:
(b) Consider the question "what is the probability of randomly drawing a 5-card hand with no face cards"? Then you could say
(40/52)*(39/51)*(38/50)*(37/49)*(36/48) = 0.2531812725090036
or
C(40,5)/C(52/5) = 0.2531812725090036
and get the same answer.
(c) But now consider "what is the probability of randomly drawing a 5-card hand with exactly one face card"? Let's try the two techniques:
(40/52)*(39/51)*(38/50)*(37/49)*(12/48) = 0.0843937575030012
but
C(40,4)*C(12,1)/C(52/5) = 0.421968787515006
The first is larger by a factor of 5, because with permutations you don't know where the face card is and you have 5 patterns to account for:
FNNNN, NFNNN, NNFNN, NNNFN, NNNNF
and each of these will have the probability (40/52)*(39/51)*(38/50)*(37/49)*(12/48) . Note that for (b), the single pattern would be larger by a factor of 1 (i.e., the same) because there is only 1 pattern:
NNNNN.
I guess the moral is that when doing these kinds of problems, think about the patterns of different components of the event; if there is a uniform set of available options, then there is only one pattern, and you can use either (because they differ by a factor of 1); if there are disjoint sets of available options, then you need to work out the m patterns, and if you use k-permutations, you would have to multiply by m. Usually, it is best to try combinations first, since you avoid having to think about all possible patterns.
English to Math!
Here is a list of some common and sometimes confusing phrases and their precise interpretation; when phrases are essentially equivalent, I will list them together.
English Phrase(s) Mathematical Meaning