Home | Applied Mathematics & Statistics



V.1 Two Counting PrinciplesAddition Principle: If there are m different sets and the first set has r1 different objects, the second set r2 different objects, . . . and the mth set rm different objects, and if the sets are disjoint, then there are r1 + r2 + . . . + rm ways to pick an object from one of the sets.Multiplication Principle: If a procedure can be broken into m stages, with r1 outcomes in the first stage, r2 outcomes in the second stage, . . . andrm outcomes in the mth stage, if the number of outcomes at each stage is independent of choices in previous stages, and if the composite outcomes are all distinct, then there are r1 x r1 x . . . x rm composite outcomes. Example 2: Arranging BooksThere are 5 (different) Spanish books, 6 French books, and 8 Transylvanian books. How many ways to pick an (unordered) pair of two books, not both of the same language. This problem uses both the Addition Principle and the Multiplication Principle. We have to break the problem into several (disjoint) cases- the Addition Principle- i) a Spanish and a French book - 5x6 ways ii) a Spanish and a Transylvanian book – 5x8 ways iii) a French and a Transylvanian book – 6x8 ways Final answer: 5x6 + 5x8 + 6x8 (do not evaluate)Example 3: Sequences of LettersHow many ways are there to form a 3-letter sequence using the letters a, b, c, d, e, and f if:a) repetition allowed _ _ _ 6 6 6 b) no repetition allowed _ _ _ 6 5 4 c) no repetition allowed and must contain e break into 3 cases based on location of the e: _ e _ 5 1 4 d) repetition allowed and must contain e Tricky – try c)’s approach: 3 cases like e _ _ 1 6 6 Must break into different cases based on the number of e’sone e: 3 subcases e _ _ two e’s: 3 subcases e e _ 1 5 5 1 1 5three e’s: 1 subcase e e e Total: 3x(1x52)+3(12x5) + 1(1) 1 1 1 Example 4: CollectionsHow many different non-empty collections can be formed from five identical apples and eight identical oranges? As we try to enumerate the number of collections, a critical question is: how do we differentiate one outcome from another. What matters is how many apples and how many oranges. Initially, it is helpful not to worry about assuring a non-empty collection (that is, include the empty collection).Then a collection is made up of some number of apples- 0,1,2,3,4 or 5- and similarly for oranges – 0,1,2,3,4,5,6,7 or 8. ANS: 6x9 different collections 6x9 – 1 non-empty collections V.2 Permutations and CombinationsA permutation of n distinct objects is an arrangement or ordering of the n objects.An r-permutation is an arrangement using just r of the n objects, written P(n,r).An r-combination of n distinct objects is an unordered collection, or subset, of r out of the n objects, written C(n,r).P(n,n) = n x n-1 x n-2 . . . x 2 x 1 = n!P(n,r) = n x n-1 x n-2 . . . x (n-r+1) = n!/(n-r)! Count P(n,r) in terms of first picking all possible C(n,r) subsets and followed by the r! ways to arrange each subset. P(n,r) = C(n,r) r! orC(n,r) = n 2912368-1204422623648-143122C(n,r) is also written as r , a binomial coefficient-- pronounced ‘n choose r’.Example 1: Ranking WizardsAmong all rankings of n wizards, what fraction has Gandalf in fifth place. A ranking is an arrangement of the n wizards and so there are n! different rankings (the denominator of our fraction). Now consider the rankings with Gandalf in fifth place. As with arrangements that include e, we list the rankings with dashes and consider the choices for the other positions.___ ___ ___ ___ _G_ ____ ___ . . . . . 1 ANS: /n!Example 2: Arrangements with Repeated LettersHow many ways to arrange the letters in SYSTEMS? How many ways if the S’s are consecutive? There are two ways to solve this problem.A.) First let us position the S’s in __ E T __ Y __ M . Since the S’s are identical, we cannot argue that there are 7 places for the first S, 6 for the second S, and 5 for the third S. Instead we need to pick a SUBSET of positions for the S’s,C(7,3). After this there are 4 remaining positions and 4 remaining (distinct) letters- arranged in 4! ways. Ans: C(7,3)4!B.) The second way is to place the other 4 letters first. NOTE that instead picking a letter for the first position, then a letter for the second position, we are now picking positions for successive letters: 7 choices for Y, 6 for T, 5 for E and 4 for M, altogether, 7x6x5x4 = 7!/3! ways (=P(7,4) ). Now we place the S’s in the 3 remaining positions—1 way, because they are identical. The two answers are identical because C(7,3)4! = (7!/3!4!)4! = 7!/3!A card deck has 52 cards, each card has a suit and a ‘kind’ or value:Suits: spades, hearts, diamonds, and clubsKinds: Ace, King, Queen, Jack, 10, 9 ,8 ,7 ,6 ,5 ,4 ,3 ,2.Example 4: Poker Probabilitiesa) How many 5-card poker ‘hands’ (subsets) are there? There are C(52,5) subsets of 5 cards chosen from 52 cards.b) What is the probability a random 5-card hand contains 3, but not 4, Aces? By ‘probability’, we mean the fraction of 5-card hands with 3, but not 4, Aces. So the denominator is C(52,5). For the numerator, we need to construct all hands with exactly 3 Aces and 2 non-Aces. We can combine any of the C(4,3) triples of Aces with any of the C(48,2) pairs of non-Aces By the product rule for the numerator, the answer is C(4,3)xC(48,2)/C(52,5). Example 5: Forming CommitteesA committee is to be formed from some of seven women and four men.a) How many committees of 3 women and 2 men? Like the Aces and non-Aces parts of the 5-card hand, we combine any of the C(7,3) triples of women with any of the C(4,2) pairs of men. Ans: C(7,3)xC(4,2). c) How any committees with 4 people and one is Mr. Baggins? This is like the rankings with Gandalf 5th but now with subsets. We take as given that Mr. Baggins is on the committee.What can vary is the subset of 3 other people who are chosen from the (7+4)-1 other people [men and women are irrelevant]d) How many committees with 4 people and at least two are women? We can try to do this part like the previous part: first pick any of the C(7,2) pairs of women and then combine with any C(11-2,2) pairs of remaining people. ANS: C(7,2)xC(9,2). BEWARE: In this problem, we cannot break the committee into two parts. Consider the choice {W1,W2,W5,M3}. Which two of the 3 women were the first pair of women? In our expression C(7,2)xC(9,2), we could have:a) first picked W1,W2, followed by W5,M3.b) first picked W1,W5, followed by W2,M3.c) first picked W2,W5, followed by W1,M3.This problem gives rise to our Set Composition PrincipleWhen counting subsets by combining two parts (i.e., using the Product Rule), the possible members of the first part must be disjoint from the possible members of the second part. That is, given any set S that is one of the outcomes being counted, we must be able to tell which elements of S are in the first part in the counting formula and which elements of S are in the second part.So in our last committee composition problem, we have to pick all the women in one step and all the men in a second step.To do this, we must break the enumeration into parts based on the number of women in the subset No. of women, No. of men 2 2 C(7,2)xC(4,2) + 3 1 C(7,3)xC(4,1) + 4 0 C(7,4)While one’s natural instinct is solving counting is to worry about missing some outcomes in your formula, the actual problem is counting outcomes more than once. This is particularly true for complicated subset problems. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download