Counting (E1) Flashcards
Homework and Exam questions related to counting. Common techniques: - permutation - combination - sum rule - product rule - balls in boxes (special case of combination)
Given a set A = {r, e, a, s, o, n}, how many different sequences of type A of length 4 are there?
6^4
Explanation:
product rule: 6 * 6 * 6 * 6 = 6^4
Given a set A = {r, e, a, s, o, n}, how many different sequences of type A of length 4 contain at least one vowel?
6^4 - 3^4
Explanation:
total ways - no vowel = 6^4 - 3^4
Given a set A = {r, e, a, s, o, n}, how many sequences of type A of length 4 begin or end with a vowel?
2 * (3 * 6^3) - 3^2 * 6^2
Explanation:
begins with vowel + ends with vowel - begins and ends with vowel = (3 * 6 * 6 * 6) + (6 * 6 * 6 * 3) - (3 * 6 * 6 * 3) = 2 * (3 * 6^3) - 3^2 * 6^2
Given a set A = {r, e, a, s, o, n}, how many subsets of A of size 3 contain exactly one vowel?
C(3, 1) * C(3, 2)
Explanation:
choose 1 vowel from 3 {e, a, o} and choose 2 consonants from 3 {r, s, n} = C(3, 1) * C(3, 2)
Given a set A = {r, e, a, s, o, n}, how many ways can you arrange the letters of A so that it is not the case that all of the vowels are together?
** Assume length of sequence is 4? Seems like I assumed that on the test and got it right.
6^4 - 3!4!
Explanation:
total ways - all vowels together = 6^4 - 3!4!
total ways = (# letters in set)^(length of sequence)
3! = ways to arrange “eao”
4! = treating “eao” as one unit + 3 remaining consonants (each consonant acting as a unit)
drawn out:
eao _ _ _
“all vowels together” is like the bride groom photography question
** TODO: make a better explanation
Assume a string (allowing repetition) is randomly selected from all strings of length 4 from the set A = {r, e, a, s, o, n},
What is the probability that the string begins with an ‘o’ and ends with a ‘r’?
1/6^2 = 1/36
Explanation:
(# of strings that begin with an ‘o’ and end with a ‘r’) / (total # possible strings) = 6^2/6^4 = 1/6^2 = 1/36
drawn out - number of strings that begins with an ‘o’ and ends with a ‘r’:
1 6 6 1
first slot: 1 = # ways to fill slot with ‘o’
second slot: 6 = # ways to fill slot with a letter from {r, e, a, s, o, n}
third slot: 6 = # ways to fill slot with a letter from {r, e, a, s, o, n}
fourth slot: 1 = # ways to fill slot with ‘r’
Assume a string (allowing repetition) is randomly selected from all strings of length 4 from the set A = {r, e, a, s, o, n},
What is the probability that it contains exactly one letter that is a vowel?
(4 * 3^4) / 6^4
Explanation:
exactly one letter is a vowel = (choose spot for vowel) * (choose 1 vowel from {e, a, o}) * (ways to fill 3 remaining slots with the 3 consonant choices: {r, s, n}) = C(4, 1) * C (3, 1) * 3 * 3 * 3 = 4 * 3^4
probability that exactly one letter is a vowel = (4 * 3^4) / 6^4
total number of ways to arrange the string = 6^4 = (total number of letters)^(length of string)
total process drawn out:
C(4, 1) C(3, 1) 3 3 3
Assume a string (allowing repetition) is randomly selected from all strings of length 4 from the set A = {r, e, a, s, o, n},
What is the probability that such a string contains exactly two ‘r’s given that it contains exactly two ‘o’s?
1/5^2 = 1/25
Explanation:
P(exactly 2 r’s | exactly 2 o’s) = P(exactly 2 r’s and exactly 2 o’s) / P(exactly 2 o’s) = (C(4, 2) * C(2, 2)) / (C(4, 2) * C(2, 2) * 5^2) = 1/5^2 = 1/25
C(2, 2) * C(4, 2) * 5 * 5 = (choose o’s) * (choose slots for o’s) * (# of ways to fill last 2 slots with {r, e, a, s, n})
Dr. Robert van de Geijn gave his class 25 problems and told his students that he would select 10 of them to put on their midterm. Mary can figure out how to answer 20 of the problems. What is the probability that Mary will be able to answer at least 80% of the questions on the exam?
** Note: I got this wrong, but I think this is correct? You can check Dr. Meyer’s video on sample e1 on how to do a similar problem
(C(20, 8) * C(5, 2)) / C(25, 10)
Explanation:
easiest way is to draw a table:
Practice problems | Test problems
Mary can answer: 20 | 8
Mary cannot answer: 5 | 2
——————————————————————————————-
Total problems: 25 | 10
((Out of the 20 practice problems Mary can answer, choose 8) * (Out of the 5 practice problems Mary cannot answer, choose 2)) / (Out of the 25 practice problems, choose 10 to be on the test) = (C(20, 8) * C(5, 2)) / C(25, 10)
How many solutions are there to the inequality x1 + x2 + x3 <= 8, where x1, x2, x3 are non-negative integers?
C(11, 8)
Explanation:
Balls in boxes problem. Each x is a box + add an additional box because it’s an inequality. Each ball = the integer 1. Therefore since the inequality is a maximum of 8, there are 8 balls. So there are 4 boxes and 8 balls. Use the balls in boxes equation to get the answer = C(balls + boxes - 1, balls) = C(8 + 4 - 1, 8) = C(11, 8)
** Kinda bad explanation
How many distinct permutation of the letters in “letters” are there?
7!/(2!2!)
Explanation
Classic Mississippi problem
Count of each letter: 1 'l' 2 'e' 2 't' 1 'r' 1 's'
C(7, 1) * C(6, 2) * C(4, 2) * C(2, 1) * C(1, 1)
How many distinct permutation of the letters in “letters” begin with two vowels?
5!/2
Explanation:
The only vowels are ‘e’ and there happen to be 2 of them, so fix them at the front slot. Apply this to the Mississippi problem.
Product rule:
Front slot is fixed with ‘ee’, only one way to fill it out
and
Choose 1 slot for the ‘l’ from the 5 remaining slots
and
Choose 2 slots for the 2 ‘t’s from the 4 remaining slots
and
Choose 1 slot for the ‘r’ from the 2 remaining slots
and
Choose 1 slot for the ‘s’ from the 1 remaining slot
= 1 * C(5,1) * C(4, 2) * C(2, 1) * C(1, 1)
How many distinct permutation of the letters in “letters” begin with two e’s or end with two t’s?
2 * (5!/2!) - 3!
Explanation:
Draw it out:
The ee must be at the beginning and the tt must be at the end:
ee _ _ _ tt
Fill in 3 middle slots with consonants using combination: ee C(3, 1) C(2, 1) C(1, 1) tt
C(3, 1) = Choose slot for ‘l’
C(2, 1) = Choose slot for ‘r’
C(1, 1) = Choose slot for ‘s’
How many distinct permutation of the letters in “letters” have vowels together?
6!/2!
Explanation:
Combination of Mississippi problem and bride groom problem.
Treat “ee” as one unit (hence bride groom problem)
Then treat each letter besides “ee” as a unit
Then apply the Mississippi problem:
C(6, 1) * C(5, 1) * C(4, 2) * C(2, 1) * C(1, 1) The C(5, 1) = "ee", the rest is standard choose x slots for the letter out of y remaining slots
How many distinct permutation of the letters in “letters” do not have vowels together?
7!/(2!2!) - 6!/2!
Explanation:
total distinct permutations - permutations with vowels together
See previous flashcards for explanation on how to solve.
