W8 - Counting and Combinatorics

Question 1

Inclusion and exclusion general case

Answer 1

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

• add individual sets.
• subtract sum of sizes for all interception of two sets
• subtract sum of sizes for all interception of three sets
• ect
• add the size of all of the sets AND together

Question 2

What is ordered/unordeded
and with/without replacement

with ice-cream example

Answer 2

Imagine ice-cream cone:

Ordered = I care about the which order the scoop are stacked [mint, choco is different to choco, mint] - this is permutations.

With replacement = I can pick the same flavour multiple times

Question 3

If we have a set of n elements and draw r elements from it

Ordered selection with replacement

Answer 3

n^r

Question 4

If we have a set of n elements and draw r elements from it

Ordered selection without replacement

Answer 4

nPr = n! / (n-r)!

Question 5

If we have a set of n elements and draw r elements from it

Unordered selection with replacement

Answer 5

(n+r-1) choose r

Question 6

If we have a set of n elements and draw r elements from it

Unordered selection without replacement

Answer 6

nCr = n! / [ r! * (n-r)!]