Section 2.3:Counting Techniques1Product RuleFor a task with k steps, if• there are n1options (ways) in the first step,• there are n2options (ways) in the second step,and until• there are nkoptions (ways) in the k-th step,• then, the total options (ways) of the task isn = n1n2· · · nk.2Summation RuleFor a task with k different cases, if• there are n1options (ways) in the first case,• there are n2options (ways) in the secondcase, and until,• there are nkoptions (ways) in the k-th case.• then, the total options (ways) of the tasks isn = n1+ n2+ · · · + nk.3First example of Section 2.3: example 2.19 ontextbook• A homeowner needs “a plumbing contractor”,“an electrical contractor” and “kitchen appli-cances”.• There are 12 options for choosing a plumbingcontractor, 9 options for choosing electricalcontractor, and 5 options for choosing kitchenappliances”.• The total number of ways isn = 9 × 12 × 5 = 540.4Second example of Section 2.3: example 2.20 ontextbook• A family in its health insurance needs to chooice“OB” doctor, “Pediatrician”, and “InternalMedicine” and “General Surgeons” doctors.• There are 4 options for “OB”, 3 options for“Pediatrician”, 3 options for “Internal Medicine”and 2 options for “General Surgeons”.• Then, the total number of options isn = 4 × 3 × 3 × 2 = 72.5Permutation number• Choose an ordered sequence of k objects fromn distinct objects, where 0 ≤ k ≤ n.• We can consider such problem in the followingway:– first step, choose the first object, n ways;– second step, chose the second object; sincethis object should be different from thefirst one, n − 1 ways;– until k-th step, choose the k-th object, sincethis object should be different from the pre-vious k − 1, n − (k − 1) = n − k + 1 ways.• By the product rule, the permutaion numberisPk,n= n × (n − 1) × · · · × (n − k + 1) =n!(n − k)!.6Combination number• Choose a set of k objects from n distinct ob-jects.• We can consider the permutation number isanother way:– first step, choose k different objects.– second step, order them.• It is clear that the number of ways in the sec-ond step is Pk,k= k!. Suppose the number ofways in the first step is x. By product rule,we havePk,n= x × Pk,k⇒ x =Pk,nPk,k=n!(n − k)!k!.• Thus, we have the combination number isCk,n=³nk´=n!(n − k)!k!.7Third example of Section 2.3: example 2.21 ontextbook.• There are 10 teaching assistants available forgrading papers;• 4 questions to be graded;• need to choose 4 TA and assign one questionfor each.• The total number of ways isP4,10= 10 × 9 × 8 × 7 = 5040.8Fourth example of Section 2.3: A bridge handconsists of 13 cards from a 52-card deck.• What is the probability of the 13 cards are allspades or clubs and both appeared.Answer:P =³2613´− 2³5213´= 0.0000164.• What is the probability of exactly two suits.Answer:P =³42´[³2613´− 2]³5213´= 0.0000983.9Fifth example of Section 2.3: Flip a balanced coin5 times. What is the probability of• at least one head.Answer: The compliment is “0 head”. Thus,P = 1 −³50´25= 1 −132= 0.96875.• at most four tails.Answer: it is the same as “at least one head”.Thus it is still 0.96875.• at least two heads.Answer: The compliment is not over “onehead”. Thus it isP = 1 −³50´+³51´25= 1 −632= 0.8125.• at most three tails.Answer: this is the same as “at least twoheads”. Thus the result is still 0.8125.10Sixth example of Section 2.3: there are threemales and two females waiting on a line. What isthe probability of all males and females are nextto each other.Answer: the event can be done in the followingsteps:• Choose either “MMMFF” or “FFMMM”. Wehave 2 options.• Order MMM. We have 3! options.• Order FF. We have 2! options.• The denominator has 5! options.• Thus,P =2 × 6 × 25!= 0.2.11Seventh example of Section 2.3: a bag has 6 blueballs and 4 red balls:• Randomly choose 2. What is the probabilityof “both balls are red”.Answer:P =³42´³102´=645= 0.1333.• Randomly choose 3. What is the probabilityof “all are the same color”.Answer:P =³63´+³43´³103´= 0.2.• Random choose 3. What is the probability of“all are different color”.Answer: since this is impossible, the probabil-ity is P = 0.12Eighth example of Section 2.3: A 52-card deckhas four suits: 13 clubs, 13, diamonds, 13 heartsand 13 spades, and number 1 to 13 for each suit(A = 1, J = 11, Q = 12 and K = 13).(a) Randomly choose 2, what are the probabilitiesof “they have the same number” and “theyare in the same suit”, respectively? Answer:the first is³131´³42´³522´= 0.0588and the second is³41´³132´³522´= 0.2353.(b) Randomly choose 3, what is the probability of“they are in different suits”? Answer:P =³43´³131´³131´³131´³523´= 0.3976.(c) Randomly choose 4, what is the probability of“they are in different suits”?Answer:P =134³524´= 0.1055.13Ninth example of Section 2.3: A class has 50students. What is the probability of “at least twoof them have the same birthday in month andday”? Suppose nobody was born on Feb, 29.Solution:P = 1 −P50,36536550= 1 −(365!/315!)36550=