Understanding Counting Methods: Combinations and Permutations
This content discusses various counting methods for computing probabilities, focusing on combinations and permutations. It explains the concepts of combinations (order doesn't matter) and permutations (order matters) with examples of selection and arrangement scenarios. The distinction between with replacement and without replacement situations is highlighted, along with the importance of considering the order in permutations. The number of ways to choose items from a set without considering the order is defined as a combination. The relationship between permutations and combinations is explored, showcasing how permutations are larger in number than combinations. Additionally, a practical example illustrates the application of combinations in solving a permutation problem concerning student groups.
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
Counting Rule 2 Dr. Samir B. B.
Summary of Counting Methods Counting methods for computing probabilities Combinations Order doesn t matter Permutations order matters! With replacement Without replacement Without replacement
ABC ACB BAC BCA CAB CBA ABD ADB BAD BDA DAB DBA Selecting 3 (without replacement) A B C D E 3=5! ?5 2! . . . CDE CED DCE DEC EDC ECD Permutation: Selecting k items from n items without replacement while considering the order. If the order is not a consideration, how many possible ways are there to accomplish this? 3
without replacement and the Order matters ABC ACB BAC BCA CAB CBA 3= 3! ?3 Selecting 3 (without replacement) ABC ABD ADB BAD BDA DAB DBA . . . A B C D E 3= 3! ?3 ABD 3=5! ?5 2! DEC CDE 3= 3! ?3 CDE CED DCE DEC EDC ECD The number of ways to choose 3 items from a set of 5, without considering the order, is known as a combination =?5 3 3! 4
Combination Combination: an unordered subset of k objects taken from a set of n distinct objects. The number of ways of combination of k objects from n distinct objects is denoted by the symbol Ck,n n C C n n k = ! n = = k , ( ) k ! ! k n k
Permutation VS. Combination Permutations are larger in number than combinations: e.g., the three numbers (1,2, 3), (1, 3,2) (2,3,1) , (3,1,2), (3,2,1) are all different permutations of the numbers 1, 2 and 3. However, they all represent the same combination of numbers. n k P ! n = = = , ! k n k k n C !( )! k n k
Number of permutation of 14 students={G1=4, G2=4, G3=4, G4=2} {G1, G1, G1, G1,G2, G2, G2, G2, G3, G3, G3, G3, G4,G4} 14! Solution: How to solve it by using combination 4!4!4!2! Selecting the 4 positions from 14 for G1: ?14 Selecting the 4 positions from 10 for G2: ?10 Selecting the 4 positions from 6 for G3: ?6 Selecting the 2 positions from 2 for G4: ?2 4?10 4 number of ways= ?14 4 4 2 14! 4?6 4?2 2= 4!4!4!2!
Combinations How many subsets of size 5 are there of the set {1, 2, 3, ..., 10}? 10 ) 5 , 10 ( = 10 ( ) 5 , 10 ! P = = C 5 ! 5 ! 5 ! 5 10 9 8 7 6 5 4 3 2 1 = 5 4 3 2 1 5 4 3 2 1 10 9 8 7 6 30240 = = = 252 5 4 3 2 1 120
Combinations Consider the set A = {a, b, c}. What are the 2-combinations of A? {a, b} {a, c} {b, c} ?3 What are the 3-combinations of A? {a, b, c} ?3 What are the 1-combinations of A? {a} {b} {c} ?3 2= 3 3= 1 2= 3
Combinations A certain club has 5 male and 7 female members. How many ways are there to form a 7 member committee consisting of 3 men and 4 women? Two tasks - pick a man, then pick a woman. Thus: C(7,4) C(5,3) How many ways can any 7 member committee be selected from the membership? 7 ?12
Combinations How many subsets of size 2 are there of {1, 2, ..., 20} which do not consist of two consecutive integers? Solution: Count the number of subsets which do contain two consecutive integers, then subtract from total number of subsets of size two. Clearly 19 subset contain two consecutive integers, e.g. {1,2}, {2,3}, {3,4}, ... , {19,20}. Thus: C(20,2) - 19.
Q. How many diagonals does a regular dodecagon (a twelve-sided polygon) have? Solution: C212-12
Question 3 Out of nine different pairs of shoes, in how many ways could I choose a right shoe and a left shoe, which should not form a pair? Right Shoe R1 R2 R3 R4 R5 R6 R7 R8 R9 Left Shoe L1 L2 L3 L4 L5 L6 L7 L8 L9 1 ??? ? ?9 ????? 1 ???? ?9 ??? ? 1 ????= 92 9 = 9 8 ?9 ????
Question 3: How many way you share 10 coins among 5 kids under the condition: 1. Every kid will take at least one coin 2. No restriction Solution 1. Coin Coin Coin Coin Coin Coin Coin Coin Coin Coin 2 2 4 1 1 Coin Coin Coin Coin Coin Coin Coin Coin Coin Coin 1 2 3 3 1 4 ???? ? ??? ??? ?9
Question 3: How many way you share 10 coins among 5 kids under the condition: 1. Every kid will take at least one coin 2. No restriction Solution 2. How about sharing 15 coins among 5 kids where every kid will take at least one coin 11 10 10 . 5 . 1 2 1 . 4 . 1 1 2 . 2 . 1 1 1 . 3 . 1 1 1 . 2 . 10 9 9 . 4 . 0 1 0 . 3 . 0 0 1 . 1 . 0 0 0 . 2 . 0 0 0 . 1 . Substrate one from each kid 1 1 1 1 11 0 0 0 0 10 4 ? ??? ??? ?10+5 1 ???? 4 ? ??? ??? ?10+5 1 ????
How to find the formula Question 3: How many way you share n coins among k kids under the condition: 1. Every kid will take at least one coin: ?? ? 2. No restriction (zero included): ??+? ? ? ? ? ?
Q. How many three-digit numbers abc have the property that a b c? Solution: 1 1 1 1 1 1 1 1 1 Sharing 9 coins among 4 kids without restriction ?9+4 1 4 1 Sharing 9 coins among 4 kids where some kids can receive zero 0009 a=0,b=0+0,c=0+0+0 000 0018 a=0,b=0,c=1 001 1080 a=1,b=1+0,c=1+0+8 118 . . 3501 a=3,b=8,c=8 388 . . 4230 a=4,b=6,c=9 469 . . 9000 a=9,b=9,c=9 999 Answer is C9+4-14-1 =12!/(3! 9!)=10*11*12/6=220.
Question: How many five-element subsets of {1, 2, 3, . . . , 10} contain at least one odd element? Odd={1,3,5,7,9}, Even={2,4,6,8,10} How many five-element subsets of {1, 2, 3, . . . , 10}: ??? How many five-element subsets of {1, 2, 3, . . . , 10} contain no odd element? ?? Answer= ??? ? ? ??! ?!?! ? ?= ?- ??
Question: 1. How many 3-element subsets of {1, 2, 3, . . . , 10}? 2. How many 7-element subsets of {1, 2, 3, . . . , 10}? Solution: 1. ?10 10! 7!3! 10! 7!3! 3= 7= 2. ?10 3. Why the answers are the same? ?= ?? ? ? ??
Expanding (x+y) (x+y) ? + ?2= ?2+ 2?? + ?2 1?= 2 1? ?? ?2? Coefficient of xy = ?2? ? + ?3= ?3+ 3?2? + 3??2+ ?3 (x+y) (x+y) (x+y) 2?= 3 1? ?? ?3? Coefficient of xy2 = ?3? ????????: ? ?? ?? ? ? ??????????? ?? ?6?4 ?? ? ? ????????? ?? ? + ?10= +??6?4+ 6?? ?10 4 ??????: ?10 ????????: ? ?? ?? ? ? ??????????? ?? ?7?4 ?? ? ? ????????? ?? ? + ?10 = +??7?4+ Answer=0
????????: ? ?? ?? ? ? ??????????? ?? ?6?4 ?? ? ? ????????? ?? ? + 3?10= +??6?4+ 6?? 34?10 4 ??????:34?10 ????????: ? ?? ?? ? ? ??????????? ?? ?5?5 ?? ? ? ????????? ?? 2? ?10 = +??5?5+ 5 Answer=25 15?10
Question: Determine the coefficient of x3y4 z in the expansion of 1. (x + y2 + z)6 2. (2x y 3z) 8 Answer: 1. ??????????? ?? ?3?2 2? ??: ?6 2. ??????????? ?? ?3 ?4? ??:23 14 31?8 3?3 2?1 1 4?3 3?5 1
Question: In a group of 12 people, how many ways can you form a committee of 4 people, with one person designated as the president and another as the vice president? 4 4 3 = ?10 2?10 2 ??????:?12 24
Question: Consider a group of 15 people. If everyone shakes hands with everyone else, how many handshakes take place? 2 ??????:?15 25
Question: Suppose you have a 4x4 grid of squares, and you want to paint each square either red or blue. How many different ways can you paint the grid such that no two adjacent squares (not including diagonals) have the same color? r b r b b r b r r b r b b r b r b r b r r b r b b r b r r b r b ???? ??? ???? 26
Question: Find the number of ordered triplets (a, b, c) of positive odd integers satisfying a + b + c = 98 Answer= 0 27
Question: calculate the following: 1. ?0 2. ?10 3. ?=0 10= 1 10= 1 10?10 ?= ?10 0+?10 9+ ?10 10=210 1+ +?10 9??9+ ?10 10?10 1?9? + ?10 2?8?2+ + ?10 ? + ?10= ?10+ ?10 P?? ? = 1 ??? ? = 1 ?? ??? ? ? ?????? 10= 0 10?10 ?= ?10 0 ?10 9+ ?10 2+ - ?10 1 C10 ?=0
Question: Prove the identity ?=? ? ?+1 ?= ??+1 ?? Solution: if m + 1 numbers are chosen from the set {0, 1, . . . , n}, It can be done in ??+1 When selecting m+1 numbers from the set {0,1,...,n}, this can be achieved in ??+1 ?+1,at each selection, the maximum value can be m, m+1, ,n ?+1ways. At each selection, the maximum value can range from m to n. In how many ways can you make selections such that the highest number chosen is k (k=m or m+1 or or n)? k=m: selecting the the item m and selection m items from {0,1,..,m-1} ?? k=m+1: selecting the the item m+1 and selection m items from {0,1,..,m} ??+? k=m+2: selecting the the item m+2 and selection m items from {0,1,..,m+1} ??+? k=n: selecting the the item n and selection m items from {0,1,..,n} ?? ? ? ? ? ? ? ?+1 ?= ?? ?+ ??+1 ?= ??+1 ?? + + ?? ?=?
Question: How many 3-element subsets of {1, 2, 3, . . . , 100} contain at least one element that is divisible by 2 and at least one element that is divisible by 5? Hint: The negation of Set of 3-elements contains at least one element that is divisible by 2 and at least one element that is divisible by 5 is Set of 3-elements contains odd elements or not divisible by 5 ? ? = ? ? |red set or blue set|=|red set|+|blue set|-|red set and blue set| 3 First, let's find the total number of 3-element subsets: ?100 Next, let's find the number of 3-element subsets that do not contain element divisible by 2 and do not contain any element divisible by 5. Number of odd numbers between 1 and 100 = 50. Number of numbers not divisible by 5 between 1 and 100 = 80 Number of odd numbers that are not divisible by 5 = 40. = 161700
Question: How many 3-element subsets of {1, 2, 3, . . . , 100} contain at least one element that is divisible by 2 and at least one element that is divisible by 5? A=Number of odd numbers between 1 and 100 = 100/2=50. B=Number of numbers not divisible by 5 between 1 and 100 =100-100/5= 80 A B=Number of odd numbers that are not divisible by 5 = card(B)/2=40. ?100 (?50 3+?80 3 3 ?40 3)
Bonus Question: Find the number of ordered quadruplets (a, b, c, d) of positive even integers satisfying a + b + c + d = 98 1 1 1 1 1 1 1 ? 1=3 If the zero is not accepted, ?? 1=98 quadruplets 2 1 ? 1=3 If zero is accepted ??+? 1=98 2+4 1 Find the number of ordered quadruplets (a, b, c, d) of positive odd integers satisfying a + b + c + d = 98. It is similar to number of ordered quadruplets (a, b, c, d) of positive even (not 0) 3 integers satisfying a + b + c + d = 98+4, so ?102 2 1
Question: Let n be a fixed positive integer. Find the sum of all positive integers with the following property: In base 2, it has exactly 2n digits consisting of n 1 s and n 0 s.The first digit cannot be 0. 1 ? 1 ?? 1 ? ?2? 1????????? ?? ?2? 1
Question: How many ways can I return your quizzes so that no one gets their own? Where n students are in the class Solution: We have n Quizzes, Q1,Q2, , Qn, for simplification we will note them just as 1,2,3, , n. We note P(n): number ways to return quizzes so that no one gets his own quiz If we have 1 quiz: P(1)=0 way If we have two quizzes: P(2)=1 way (12: rejected or 21: accepted) If we have three quizzes: P(3)=2 123:no, 132:no, 231:yes, 213:no, 312:yes, 321:no If we have four quizzes: P(4)=3(P(3)+p(2))=3(2+1)=9 If we have n quizzes: P(n)=(n-1)P(n-1)+(n-1)p(n-2)= Index: 1 2 .. o .. n o 1 Case 1 o Not 1 Case 2 34
Question: How many ways can I return your quizzes so that no one gets their own? Where n students are in the class Index: 1 2 .. o .. n o 1 Case 1 o Not 1 Case 2 Case 1: index o and 1 have exchanged their positions: number ways to return quizzes so that no one gets his own quiz under this case is: (n-1) P(n-2) (n-1): number of choices for index o (all except index 1) P(n-2): after removing the two indexed o and 1 at position 1 and o, remain how to do the distribution of n-2 quizzes among the n-2 position such that no one will have his own quiz, P(n-2) Case 2: index o and 1 did not exchange their positions: number ways to return quizzes so that no one gets his own quiz under this case is: (n-1) P(n-1) (n-1): number of choices for index o (all except index 1) P(n-1): after removing the indexed o, remain how to do the distribution of n-1 quizzes among the n-1 position such that no one will have his own quiz, and 1 should not in index o, P(n-1) 35
Number of set S of {1,2,,n} satisfy the condition = Kn Kn =Kn-1+Kn-2 because if S satisfies the case n-1, then S ?and if S satisfies the case n-2, then S ? 1 K2 =2 ->{1} or {1,2} K1 =1-> {1} 36
Question: Let S be the smallest set of positive integers such that (a) 2 is in S, (b) n is in S whenever n2 is in S, and (c) (n + 5)2 is in S whenever n is in S. Which positive integers are not in S? Answer. The positive integers that are not in S are 1 and the multiples of 5. Solution. First note that by combining conditions c) and b), n S implies n+5 S. Also, because 2 S, we have 72 = 49 S and therefore (49 + 5)2 = 542 S. Thus, because 542 1 (mod 5), all sufficiently large positive integers that are 1 (mod 5) are in S. Now let a > 1 be an integer that is not a multiple of 5. Then the sequence a, a2 , a4 , a8 , a16 , . . . grows without bound, and by Fermat s little theorem (or by a check of cases mod 5) all the terms of the sequence starting with a 4 are 1 (mod 5). Thus the sequence contains elements of S, and by repeated application of condition b) it follows that a S. On the other hand, it is easy to check that the set of all integers greater than 1 that are not multiples of 5 satisfies conditions a), b), and c), so this is the set S, and the complement of S consists of the integers listed in the answer. 37
