Understanding Counting Methods in Probability
This content provides an overview of counting methods for computing probabilities, including combinations and permutations with or without replacement. It explains concepts like permutation with replacement using examples, such as finding possible combinations of letters with repetition allowed. The counting rules, product (multiplication) rule, and exercises on creating unique numbers and ordering meals are also covered.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Summary of Counting Methods Counting methods for computing probabilities Combinations Order doesn t matter Permutations order matters! With replacement Without replacement Without replacement
AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC. Permutation with replacement is a concept in combinatorics that deals with arranging objects where repetition is allowed. Let's say you have a set of three letters: {A, B, C}. You want to find all the possible three-letter combinations that can be formed if you're allowed to repeat the letters. 1 2 3 A A A A A B A B C A A C A B A A B B A B C A C A A C B A C C . . . . . . C C C 27 possibilities
Permutation with replacement is a concept in combinatorics that deals with arranging objects where repetition is allowed. Let's say you have a set of three letters: {A, B, C}. You want to find all the possible three-letter combinations that can be formed if you're allowed to repeat the letters. AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC. A B C 1 2 3 A A A B B B C C C 3 3 3 27 possibilities
Car number plate Question: How many cars can be given a unique six-digit number? 106= ????{000000, ,999999} #10 #10 #10 #10 #10 #10 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
Counting Rule: Product (Multiplication) Rule If there are k elements ( or things) to choose and there are n1 choices for the first element, n2 for the second element, and so on to nk choices for the kthelement, then the number of possible ways of selecting them is n n 2 ... n 1 k Only applies when elements are different and the order of elements matters. 6
Exercise 1: Suppose each student is assigned a 5-digit number. How many different numbers can be created? CARD{00000,00001, ,99999}=105
Exercise 2: 1. Simple addition: If there are a varieties of soup and b varieties of salad, then how many ways to order a meal of soup or salad (but not both soup and salad) 2. Simple multiplication: If there are a varieties of soup and b varieties of salad, then how many ways to order a meal of soup and salad Soltion 2: 1. Simple addition: a+b possible 2. Simple multiplication: a.b possible
Exercise 3: How many license plates are possible with 3 letters followed by 3 digits? 26 26 26 10 10 10 = 17576000 Exercise 4: Suppose that you own 3 pairs of shoes, 6 pairs of socks, 4 pairs of pants, and 6 shirts. How many different outfits can you make out of these articles of clothing? 3*6*4*6 (An outfit consists of one pair of shoes, one pair of socks, one pair of pants, and one shirt.
Exercise 5: Consider the following road map. A B C a) How many ways are there to travel from A to B, and back to A, without going through C?4*4 b) How many ways are there to go from A to C, stopping once at B? A Band B C:4*2 c) How many ways are there to go from A to C, making at most one intermediate stop? One stop or zero stop. 4*2 + 1.
Exercise 6: Suppose that you flip a coin 5 times and record the sequence of heads and tails. How many possibilities are there for this sequence? 2*2*2*2*2=25 11
Exercise 7: How many unique 5-letter license plates can be created such that no two adjacent letters are the same? A A R S S B C D R E A C X T S C D X G T A Z X X Y #26 #25 #25 #25 #25 ????????: 26 254 12
Permutations and Combinations
How many permutations can be formed using the letters of the word ABC"? (no repitition)
Permutation Possible permutations of three colored balls: NUMBER OF WAYS: 3 2 1
Permutation RULE: The number of permutations of a set of n objects is the product of the first n positive integers, that is n(n -1) ... 1 = n!
Exercise 8 In how many ways can 8 people be seated in 8 aligned seats? A B C D E F G H ??????:8! E H C D A F G B In how many ways can 8 people be arranged at a round table? A F G H ??????:7! C E D B Same arrangement 17
Question: How many permutations can be formed using the letters of the word "GAUSS"? At the first you might think it is 5!, why it is wrong answer? GAUSS G A U S S Same permutation G A U . S . S . . S S U A G S Same permutation U A G S How many permutations can be formed using the letters of the word "GAUSS"???????:?! ?!
Exercise 9 : HOW MANY WORDS CAN BE FORMED BY "MISSISSIPPI" 11! ??????: 4!4!2! Exercise 10 : HOW MANY WORDS CAN BE FORMED BY "MISSISSIPPI" SUCH THAT ALL VOWELS ARE TOGETHER? MSSSSPPIIII=7!/(2!4!) MSSSSPIIIIP=7!/(2!4!) IIIIMSSSSPP=7!/(2!4!) Answer = 7!/(2!4!) *8=8!/(2!4!) - - > the 4 letters IIII will be considered as one letter The problem will look like: 8 Letters MSSSSPPI--> 8!/(4!2!) 19
Exercise 11: A palindrome is a word that can be read the same way in either direction (such as RACECAR). How many 9-letter palindromes (not necessarily meaningful) can be formed using the letters A Z? A B C D E D C B A Answer: 26 * 26 * 26 * 26 * 26 = 265 = 11,881,376 20
How many permutations can be formed using the letters of the word ABC"? ?????? ?? ?????????? ?? 3 2 1 = 3!
How many words of two letters can be formed using letters of the word ABC"? ?????? ?? ?????????? ?? 3 2
Exercise 12:How many words of three letters can be formed using letters of the word ABCDEFG"? 7 6 5 ?????? ?? ?????????? ?? 7 6 5 = 7 6 54 3 2 1 4 3 2 1 ?????? ?? ?????????? ??7! 4! Selecting 3 element without repetition (without replacement) 7! 4!= ?7 7! Set of 7 different elements 3= 7 3 !
Permutation in General Permutation: an ordered arrangement of k objects taken from a set of n distinct objects ( k n ). The number of ways of permutation of k objects from n distinct objects will be denoted by the symbol Pk,n ! n = = k n P P , k n ( )! n k an ordered arrangement of n=7 objects taken from a set of n=7 distinct objects 7 6 5 4 3 2 1
Exercise 13: In a tournament with twenty players, how many different ways can the top five competitors be ranked? 5=20! Answer:P20 15!= 20 19 18 17 16 25
Exercise 14: How many 3-digit numbers can be constructed from the digits 1, 2, 3, 4, 5, 6 if each digit may be used (i) only once; (ii) as often as desired? (iii) only once and odd and even digits must be grouped together, exp. 135426 ????????: ?) ?6 ??) 63 ???) 3!3!2 3 26
Exercise 15: In a group of 10 friends, they want to take a photo together. However, they want to arrange themselves in such a way that no two friends who have had an argument in the past are standing next to each other. How many different arrangements are possible? ????????: 10! 9! 2! Number of arrangement such that the two friends who have had an argument are standing next to each other A A G G H H C C F EG D D B B E E EG F A B C D E F G H I J A B C D F EG H I J 9!???????????? A A G G H H C C EG GE D D B B E E F F 10 9 friends friends 9!2! ???????????? 27
Exercise 16: Eight boys and nine girls sit in a row of 17 seats. 1. How many different seating arrangements are there? 2. How many different seating arrangements are there if all boys sit next to each other, and all the girls sit next to each other? 3. How many different seating arrangements are there if no child sits next to a child of the same sex? ??????: 1) 17! 2) ? ?? ? ?? ? ? ? ? 8!9!2! 3) ??????..?? 8!9! BGBGBGBGBGBGBGG 28
Exercise 17: Find total number of subsets of the set ? = 1,2,3,4,5,6,7,8 Examples: , 1,2,3,4,5,6,7,8 , {1}, {2,3,5}, Exercise 18: Which are there more of among the natural numbers between I and 1,000,000: numbers that can be represented as a sum of a perfect square and a (positive) perfect cube, or numbers that cannot be? ?????? ?? ???????? ? ??? ? ?? ? = ?2+ ?3 106 Solutions: 17. Examples: , 1,2,3,4,5,6,7,8 , {1}, {2,3,5}, -> number of subsets is 28 18. ?????? ?? ???????? ? ??? ? ?? ? = ?2+ ?3 106 if n = 1 12+ ?3 106 ? if m = 1 ?2+ 13 106 ? 106 1 ? = 1,2, ,999 The count of solutions is below 100,000 (100 * 1000 = 105). Conversely, the numbers that cannot be expressed as the sum of a perfect square and a perfect cube surpass 900,000 (106 - 105 = 9 * 105) 3106 1 ? = 1, ,99 Answer: There are more numbers that cannot be expressed as the sum of a perfect square and a perfect cube 29
Solutions: 1. Examples: , 1,2,3,4,5,6,7,8 , {1}, {2,3,5}, -> number of subsets is 28 2. ?????? ?? ???????? ? ??? ? ?? ? = ?2+ ?3 106 if m = 1 ?2+ 13 106 ? Possible value of n are only 1,2, ,999 106 1 ? = 1,2, ,999 3106 1 ? = 1, ,99 if n = 1 12+ ?3 106 ? if n = 999 9992+ ?3 106 ? 3106 999 ? = 1, ,99 Number of solution is 99*999 numbers that can be written as perfect square plus perfect cube are bigger than 106-99*999 Answer: Numbers that cannot be a sum of a perfect square and a (positive) perfect cube are more 30
