Combinatorics + Probability Flashcards
What is the product principle?
n(A and B) = n(A) x n(B)
Where n(A) means the number of ways of making a choice about A.
When would you use the product principle?
When you wish to select one option from A and one option from B, you use the product principle
When would you use the addition principle?
When you wish to select one option from A or one option from B, where A and B are mutually exclusive, you can use the addition principle.
When can’t you use the addition principle?
When the choices for A and B overlap, i.e. odd and prime numbers on a dice. The choices must be mutually exclusive.
In a class there is an award for best mathematician, best sportsperson, and nicest person. People can receive more than one award. In how many ways can the awards be distributed if there are 12 people in the class?
Product principle:
N(A + B +C)
= 12 x 12 x 12
= 1728
An examination has 10 questions in section A and 4 questions in section B. Calculate how many different ways there are to choose questions if you must choose:
a) one question from each section
b) a question from either section A or section B
a) AND => Product principle
10 x 4 = 40
b) OR => Addition principle
10 + 4 = 14
State how many ways:
a) 4 distinguishable toys can be put into 3 distinguishable boxes
b) 3 distinguishable toys can be put into 5 distinguishable boxes
a) 3^4 = 81
b) 5^3 = 125
The number of permutations (arrangements of n distinct objects
n!
A seven digit number is formed by using each of the digits 1 to 7 exactly once. How many such numbers are even?
Pick the final digit to be even (3 ways)
AND
then permute the reamining 6 digits (6! ways)
=> 3 x 6! = 2160
How many permutations of the letters of the word SQUARE start with 3 vowels
Permute the 3 vowels at the beginning (3! ways)
AND
permute the 3 consonants at the end (3! ways)
Number of ways = 3! x 3! = 36
What is the formula for the number of ways of choosing r objects from n objects?
nCr = n!/(r!(n-r)!)
What is the exclusion principle?
When you count what you are not interested in and subtract it from the total
How many 5-digit codes formed by using each of the digits 1 to 5 exactly once do not end in ‘25’?
How could you do this without using the exclusion principle?
Pick the final digit from {1,2,3,4}(4 ways)
AND
permute the remaining 4 digits (4!)
OR pick the final digit as 5 (1 way)
AND pick the penultimate digit from {1,3,4}(3 ways)
AND permute the remaining 3 digits (3! ways)
(4 x 4!) + (1 x 3 x 3!) = 114
How many 5-digit codes formed by using each of the digits 1 to 5 exactly once do not end in ‘25’?
How would you do this using the exclusion principle?
Count permutations of 5 digit codes (5!) ways
then exclude cases where the last two digits are 25 (1 way)
AND
Permute the remaining 3 digits (3! ways)
5! - 1 x 3! = 114
Theo has 8 different jigsaws and 5 different bears. He chooses 4 toys. In how many ways can he make a selection with at least 2 bears?
HINT: use the exclusion principle
Count combinations of 4 toys from 13 (13C4 ways)
then exclude combinations with no bears AND 4 jigsaws (5C0 x 8C4)
OR
one bear AND 3 jigsaws (5C1 x 8C3)
Number of ways = (13C4 - (5C0 x 8C4 + 5C1 x 8C3))
=365
Seven numbers are chosen from the integers between 1 and 19 inclusive. State how many selections have:
a) at most 2 even digits
b) at least 2 even digits
How many selections of 7 are possible -> 19C7 ways = 50388
9 even numbers between 1 and 19
a) At most 2 even = 0 even + 1 even + 2 even
0 even = 10C7, 1 even = 9C1 x 10C6, 2 even = 9C2 x 10C5
n(at most two even) = 11082
b) At least 2 even = 19C7 - 0 even - 1 even
n(at least 2 even) = 48378
A class of 28 pupils needs to select a committee consisting of a class representative, treasurer, and football captain. Each post needs to be taken by a different person.
In how many different ways can the four posts be filled?
Choose 4 from 28 (28C4 ways)
AND permute those (4! ways)
Number of ways = 28C4 x 4! = 491400
The general formula for this is using the nPr formula = nCr x n!
The number of permutations of a subset of size r from a set of n distinct objects is
nPr = n!/(n-r)!
A class of 18 needs to select a committee consisting of a President, a Secretary, and a Treasurer.
How many different ways are there to form the committee if one student, Ellie, does not want to be President?
Using exclusion principle:
how many ways are there?
18C3 x 3! = 18P3
How many ways where Ellie is President?
1 x 17C2 x 2! = 17P2
How many ways where Ellie isn’t president?
18P3 - 17P2 = 4624
How do you address a problem where two objects must remain together?
Example: anagrams of the word SQUARE where QU are next to each other
The trick is to imagine the letters in the word SQUARE as being on tiles. If Q and U need to be together, you are dealing with 5 tiles, one containing QU:
|S|QU|A|R|E|
However you must also remember that the condition is satisfied if the Q and U are in the other order
|S|UQ|A|R|E|
How many permutations of the word SQUARE have the Q and the U next to each other?
Permute the 5 ‘tiles’, as one is |QU| (5! ways)
AND
permute the letters QU on the ‘double tile’ (2! ways)
Number of ways = 5! x 2! = 240
What do you do if some of the objects must be separated?
If some of the objects must be kept apart, permute the remaining objects and then insert the separated objects into the gaps.
How many permutations of the word SQUARE have none of the vowels together?
Permute the 3 consonants (3! ways)
_ Q _ R _ S _ .
AND choose 3 out of the 4 gaps (4C3 ways)
AND Permute the three vowels to put into the gaps (3! ways)
Total number of ways = 3! x 4 x 3! = 144
In a photo there are 3 families - 6 Greens, 4 Browns, and 7 Grays - arranged in a row. The Browns have had an argument among themselves so they refuse to stand next to each other. How many different permutations are permitted?
G_G_G_G_G_G_G_G_G_G_G_G_G
Permute Greens and Grays: 13! ways
AND Select 4 gaps to put the Browns into: 14C4 ways
AND permute the Browns in their spaces: 4! ways
13! x 14C4 x 4! = 1.496x10^14
In a cinema there are 15 seats in a row. State how many ways can the 7 friends be seated in the same row if:
a) there are no restrictions
b) they all want to sit together
a) choose the seats AND permute
15C7 x 7! = 32432400
b) choose the seats (treating 7 seats as one) AND permute
9C1 x 7! = 45360
If there are n objects with rA of type A, rB of type B, rC of type C etc. then the number of permutations is:
n!/(rA! x rB! x rC! x …)
Find the number of arrangements of the letters MATHEMATICS
There are 11 letters, of which two are Ms, two Ts, and two As. All the other letters occur once. You could put in a 1! in the denominator to represent these.
.11!.
.———-.
2! x 2! x 2!
= 4989600
To find the probability of an event labelled A occurring, you find…
P(A) = number of outcomes in which A occurs / total number of possible outcomes
A committee of 4 is randomly chosen from 6 girls and 5 boys. What is the probability that the committee contains exactly 3 girls?
Total number of committees:
11C4 = 330
Choosing 3 girls from 6 and 1 boy from 5 can be done in:
6C3 x 5C1 = 100 ways
P(exactly 3 girls)= 100/330
