Statisticsljdhciwjhf[wp ofpwifovikjdjheo iw

Study with care

1. Counting techniques The branch of mathematics that deals with the various counting techniques is called combinatorics . There are three basic counting techniques. They are multiplication rule , permutation and combination .

2. Fundamental Counting Principle Fundamental Counting Principle can be used to determine the number of possible outcomes when there are two or more characteristics . Fundamental Counting Principle states that if an event has m possible outcomes and another independent event has n possible outcomes, then there are m * n possible outcomes for the two events together.

3. Fundamental Counting Principle Let’s start with a simple example. A student is to roll a die and flip a coin. How many possible outcomes will there be? 1H 2H 3H 4H 5H 6H 1T 2T 3T 4T 5T 6T 12 outcomes 6*2 = 12 outcomes

4. Fundamental Counting Principle For a college interview, Robert has to choose what to wear from the following: 4 slacks, 3 shirts, 2 shoes and 5 ties. How many possible outfits does he have to choose from? 4*3*2*5 = 120 outfits

5. Permutations A Permutation is an arrangement of items in a particular order. Notice, ORDER MATTERS ! To find the number of Permutations of n items, we can use the Fundamental Counting Principle or factorial notation.

6. Permutations The number of ways to arrange the letters ABC: ____ ____ ____ Number of choices for first blank ? 3 ____ ____ 3 2 ___ Number of choices for second blank? Number of choices for third blank? 3 2 1 3*2*1 = 6 3! = 3*2*1 = 6 ABC ACB BAC BCA CAB CBA

7. There are basically two types of permutation: Repetition is Allowed : such as selecting three digits to form a lock. It could be "333". No Repetition : for example the first three people in a running race. You can't be first and second.

8. Thus , n P r represents the number of ways r positions can be filled from n objects .

9. 12 Permutation formula proof There are n ways to choose the first element n -1 ways to choose the second n -2 ways to choose the third … n - r +1 ways to choose the r th element By the product rule, that gives us: P ( n , r ) = n ( n -1)( n -2)…( n - r +1)   Each of the n P r arrangements is called a permutation of n objects taken r at a time.

10. Permutations To find the number of Permutations of n items chosen r at a time, you can use the formula

11. Permutations A combination lock will open when the right choice of three numbers (from 1 to 30, inclusive) is selected. How many different lock combinations are possible assuming no number is repeated? Practice:

12. Permutations A combination lock will open when the right choice of three numbers (from 1 to 30, inclusive) is selected. How many different lock combinations are possible assuming no number is repeated? Practice:

13. Permutations From a club of 24 members, a President, Vice President, Secretary, Treasurer and Historian are to be elected. In how many ways can the offices be filled? Practice:

14. Permutations From a club of 24 members, a President, Vice President, Secretary, Treasurer and Historian are to be elected. In how many ways can the offices be filled? Practice:

15. Combinations A Combination is an arrangement of items in which order does not matter. ORDER DOES NOT MATTER! Since the order does not matter in combinations, there are fewer combinations than permutations.  The combinations are a "subset" of the permutations.

16. Combinations To find the number of Combinations of n items chosen r at a time, you can use the formula

17. There are also two types of combinations (remember the order does not matter now): Repetition is Allowed : such as coins in your pocket (5,5,5,10,10) No Repetition : such as lottery numbers (2,14,15,27,30,33)

18. Combinations Practice: How many committees of two chemists and one physicist can be formed from 4 chemists and 3 physicists?

19. Combinations A student must answer 3 out of 5 essay questions on a test. In how many different ways can the student select the questions? Practice:

20. Combinations A basketball team consists of two centers, five forwards, and four guards. In how many ways can the coach select a starting line up of one center, two forwards, and two guards? Practice:

21. Combinations A basketball team consists of two centers, five forwards, and four guards. In how many ways can the coach select a starting line up of one center, two forwards, and two guards? Practice: Center: Forwards: Guards: Thus, the number of ways to select the starting line up is 2*10*6 = 120 .

22. 25 Permutations vs. Combinations Both are ways to count the possibilities The difference between them is whether order matters or not Consider a poker hand: A ♦ , 5 ♥ , 7♣, 10♠, K♠ Is that the same hand as: K♠, 10♠, 7♣, 5 ♥ , A ♦ Does the order the cards are handed out matter? If yes, then we are dealing with permutations If no, then we are dealing with combinations

23. 26 Permutations vs. r -permutations r -permutations: Choosing an ordered 5 card hand is P (52,5) When people say “permutations”, they almost always mean r -permutations But the name can refer to both Permutations: Choosing an order for all 52 cards is P (52,52) = 52! Thus, P ( n , n ) = n !

24. 27 Combination formula proof Let C (52,5) be the number of ways to generate unordered poker hands The number of ordered poker hands is P (52,5) = 311,875,200 The number of ways to order a single poker hand is P (5,5) = 5! = 120 The total number of unordered poker hands is the total number of ordered hands divided by the number of ways to order each hand Thus, C (52,5) = P (52,5)/ P (5,5)

25. 28 Combination formula proof Let C ( n , r ) be the number of ways to generate unordered combinations The number of ordered combinations (i.e. r -permutations) is P ( n , r ) The number of ways to order a single one of those r -permutations P ( r, r ) The total number of unordered combinations is the total number of ordered combinations (i.e. r -permutations) divided by the number of ways to order each combination Thus, C ( n, r ) = P ( n, r )/ P ( r, r )

26. 29 Combination formula proof

27. 30 Corollary 1 Let n and r be non-negative integers with r ≤ n . Then C ( n , r ) = C ( n , n-r ) Proof:

28. 31 Corollary example There are C(52,5) ways to pick a 5-card poker hand There are C(52,47) ways to pick a 47-card hand P(52,5) = 2,598,960 = P(52,47) When dealing 47 cards, you are picking 5 cards to not deal As opposed to picking 5 card to deal Again, the order the cards are dealt in does matter

29. 32 An alternative (and more common) way to denote an r -combination: I’ll use C( n , r ) whenever possible, as it is easier to write in PowerPoint A last note on combinations

30. Permutations with Indistinguishable Objects Some elements may be indistinguishable in counting problems. When this is the case, care must be taken to avoid counting things more than once. EXAMPLE: How many different strings can be made by reordering the letters of the word SUCCESS ?

31. Solution: Because some of the letters of SUCCESS are the same, the answer is not given by the number of permutations of seven letters. This word contains three S s , two C s, one U , and one E . To determine the number of different strings that can be made by reordering the letters, first note that the three S s can be placed among the seven positions in C( 7 , 3 ) different ways, leaving four positions free. Then the two C s can be placed in C( 4 , 2 ) ways, leaving two free positions. The U can be placed in C( 2 , 1 ) ways, leaving just one position free. Hence E can be placed in C( 1 , 1 ) way. Consequently, from the product rule, the number of different strings that can be made is

32. C( 7 , 3 )C( 4 , 2 )C( 2 , 1 )C( 1 , 1 ) = = =420  

33. In general, for counting in which some elements are indistinguishable, the following theorem holds: The number of different permutations of n objects, where there are n 1 indistinguishable objects of type 1, n 2 indistinguishable objects of type 2 , . . . , and n k indistinguishable objects of type k , is  

34. Proof: To determine the number of permutations, first note that the n 1 objects of type one can be placed among the n positions in C(n, n 1 ) ways, leaving n − n 1 positions free. Then the objects of type two can be placed in C(n − n 1 , n 2 ) ways, leaving n − n 1 − n 2 positions free. Continue placing the objects of type three , . . . , type k − 1, until at the last stage, n k objects of type k can be placed in C(n − n 1 − n 2 −· · ·− n k − 1 , n k ) ways. Hence, by the product rule, the total number of different permutations is

35. C(n, n 1 )C(n − n 1 , n 2 ) · · · C(n − n 1 −· · ·− n k − 1 , n k ) = =  

36. Examples How many different strings can be made from the letters in MISSISSIPPI , using all the letters? How many different strings can be made from the letters in ABRACADABRA , using all the letters?

37. Test your knowledge How many ways are there to select 12 countries in the United Nations to serve on a council if 3 are selected from a block of 45, 4 are selected from a block of 57, and the others are selected from the remaining 69 countries? Hence find the probability of selecting these 12 countries to serve on the council.

38. An urn contains 3 red balls, 2 green balls and 1 yellow ball. Three balls are selected at random and without replacement from the urn. What is the probability that at least 1 color is not drawn ? A box contains four $10 bills, six $5 bills and two $1 bills. Two bills are taken at random from the box without replacement. What is the probability that both bills will be of the same denomination?

39. A urn contains n black balls and n white balls. Three balls are chosen from the urn at random and without replacement. What is the value of n if the probability is 1/12 that all three balls are white?

40. A bag contains 5 different science books, 4 different history books, and 3 different mathematics books. If 5 books are selected at random from the bag, find the probability that they contain Exactly 2 science books 2 science books, 2 history books and 1 mathematics book.

41. 4 Mathematics books, 3 Chemistry books, 2 Physics books, and 1 Biology book are to be arranged on a bookshelf. How many different arrangements are possible if the books in each particular subject must all stand together, only the Mathematics books must be in the first position on the shelf whilst the others must also always be together but not in the first position . all the subject matters can be arranged anyhow except the Chemistry books. A group contains n men and n women. How many ways are there to arrange these people in a row if the men and women alternate? A deck of cards contains 10 red cards numbered 1 to 10 and 10 black cards numbered 1 to 10. How many ways are there of arranging the 20 cards in a row? Suppose we draw the cards at random and lay them in a row. What is the probability that red and black cards alternate?

42. If there are 4 Czech tennis players, 4 U.S. players, and 3 Russian players at the U.S. Open Tennis Championship, how many ways could they be arranged?

43. The internal telephone numbers in the phone system on a campus consist of five digits, with the first digit not equal to zero. How many different numbers can be assigned in this system?

44. Suppose a box contains 4 blue, 5 white, 6 red and 7 green balls. In how many of all possible samples of size 5, chosen without replacement , will every colour be represented ? Hence estimate the probability of this selection.   Show that if n is a positive integer, then - = n 2  

45. A witness to a hit-and-run accident tells the police that the license plate of the car in the accident, which contains three letters followed by three digits, starts with the letters AS and contains both the digits 1 and 2. How many different license plates can fit this description? Answer: 26 P 1 * 2 P 2 * 10 P 1 =520