In a race with 10 participants, how many possible top 3s are there?
10 x 9 x 8 = 720
How many subsets are there of a set A of size |A|?
2^|A| To make a subset we can go through every element in the set and make a binary choice to include or exclude it from the subset. Thus there are |A| successive choices and 2 ways to make each one, hence there are 2^|A| possible subsets.
How many passwords of length 6 are there, assuming passwords can use any upper or lowercase letter, underscores, digits and must contain at least 1 digit?
There are 26 lowercase letters, 26 uppercase letters, 1 underscore and 10 digits. So there are 26 +26+1+10 = 63 choices for each character and we make 6
choices. This gives 63⁶ different choices. However many of these have no digits.
If we don’t use any digits there are 26 + 26 + 1 = 53 choices for each character
so only
63⁶ −53⁶
What is the inclusion-exclusion principle?
Overcount, then subtract off the amount you overcounted by. |A∪B|=|A|+|B|−|A∩B|
What is the pigeonhole principle?
If you have more pigeons than holes, some of them will have to share. If n>k objects are placed in k boxes then at least one
box will contain two or more objects. In particular if k+1 objects are placed into k boxes at least one box will contain at least 2 objects.
What is the generalised pigeonhole principle?
If n > k objects are placed in k boxes then
at least one box will contain ⌈N/k⌉ objects.
What is the smallest number of unique words you can choose so that you are guaranteed to have two that start with the same letter?
- There are k = 26 letters in the alphabet, creating 26 pigeonholes. Each word is
a pigeon, so we need at least n = 26+1 of them to ensure that at least two
occupy the same hole.
How many people do you need to guarantee that at least two of them share a birthday?
- There are 365 days (holes), so we need at least 366 people (pigeons) to
guarantee this.
In a room of 100 people, what is a lower bound on the number born in the same month?
- There are 100 people (pigeons), and 12 months (holes), using the generalised pigeonhole principle this gives at least ⌈100/12⌉ = 9 people who were born in the same month.
What is the similarity and difference between permutations and combinations?
They both don’t include replacement. Permutations is used when the order matters, combinations is used when the order is irrelevant.
What is the formula for permutations? P(n,k) = …
n(n−1)(n−2)…(n−k+1) = n!/
(n−k)!
How many different strings of length 3 are there can be made from the string ‘TONGUE’?
P(6,3) = 6!/3! = 720/6 = 120 Here order matters, since we don’t consider ‘TON’ the same string as ‘NOT’.
Because all the characters are distinct we can apply the formula directly.
How many length 4 strings can be made from the characters ‘ABC’?
3 x 3 x 3 x 3 = 3⁴ = 81
What is the formula for combinations? C(n,k) = …
C(n,k) = P(n,k)/k! = n!/(n-k)!k!
What are n and k in permutations and combinations?
The number of ways to select k items from n without replacement where 1 <= k <= n
What is P(n,k) in terms of combinations?
P(n,k)=C(n,k)k!
How many ways are there to select 5 red and 5 blue balls from a bowl containing 50 red and 50 blue balls?
C(50,5) × C(50,5) = 4,489,143,937,600
How many ways are there to put 7 indistinguishable stars, *, into 5 distinguishable bins ||?
C(11,7) = 330. The length is 7 +5−1 since we insert 5 −1 bars between 7 stars. We need to choose 7 of these positions to be stars, and the rest are bars. The number of ways to do this (since the order of the stars is irrelevant) is
C(7 +5−1,7) = 330
How many ways are there to choose 5 coins from a bag of 1p, 2p, 5p, 10p, 20p, 50p coins? Assume there are at least 5 of each type of coin in the bag.
C(10,5) = 252. Use stars and bars. There are 5 items to choose so k=5 and there are 6 options to choose from so n=6. This means there are 6 bins with 5 stars spread between the bins so there are 10 positions because k+n-1 = 5+6-1 = 10. Therefore you have 10 positions and 5 need to be stars (coins), so the answer is C(10,5) = 252.
What is the formula for combinations with replacement?
C(n+k-1, k)
What is the formula for permutations with replacement?
nᵏ
