Sets and Counting

Set Notation #

Unions, intersections and the universal set.

A set is a collection, and the universal set is everything under discussion

A set is a collection of distinct objects. This one is called A.

The box around it is the universal set: everything we are talking about.

Now add a second set, B. 2 of the 4 elements of A are in B as well.

That overlap is the intersection, $A\cap B$A ∩ B: in A and in B at the same time.

Everything in either circle is the union, $A\cup B$A ∪ B: in A, in B, or in both.

Venn Diagrams #

Two sets make four regions, three make eight.

A Venn diagram splits the universal set into regions that never overlap

2 circles make 4 regions: only A, both, only B, and neither.

3 circles make 8 regions, counting the one outside them all.

Fill the middle region first and work outward, or you will double-count.

Complements and Subsets #

Everything that is not in the set.

The complement of a set is everything in the universal set that is not in it

7 elements are in A, and 13 are not. Those 13 are its complement.

A set and its complement together make up the whole universal set.

If every member of B is also in A, then B is a subset of A: $B\subseteq A$B ⊆ A.

Cantor’s Diagonal: Bigger Infinities #

Some endless things cannot even be listed.

The decimals between 0 and 1 cannot be listed even in an endless list

The whole numbers are endless, yet you can list them in order: 0, 1, 2, 3 and so on.

Now suppose the decimals are listed. The shaded digits run down the diagonal: 4, then 7, then 3.

Change every diagonal digit: 0.584 differs from every row, so this list has missed it.

Counting a Union #

Add both, then take the overlap off once.

Adding two sets counts their overlap twice, so subtract it once

A has 12 members and B has 9, but the total is not 21.

The 5 in the overlap were counted in A and again in B.

So subtract the overlap once: $n\left(A\cup B\right)=12+9-5=16$n(A ∪ B) = 12 + 9 − 5 = 16.

Probability in Set Notation #

Saying exactly which outcomes you mean.

Set notation says exactly which outcomes a probability is counting

There are 20 outcomes in all: 6 in A only, 4 in both, 5 in B only, and 5 in neither.

$P\left(A\cap B\right)$P(A ∩ B) counts only the overlap: $\frac{4}{20}$4/20.

$P\left(A\cup B\right)$P(A ∪ B) counts all three shaded regions: $\frac{15}{20}$15/20.

Conditional Probability from Tables #

The given row’s total is the new denominator.

A condition narrows the table to one row and that row’s total becomes the denominator

A two-way table answers “given” questions: each condition narrows the table.

Given walks, only the walks row counts — its total 12 is the new denominator.

Of those 12 walkers, 7 are girls: $P\left(\text{girl}|\text{walks}\right)=\frac{7}{12}$P(girl | walks) = 7/12, read from one row alone.

Adding and Multiplying Choices #

Steps in a row multiply; alternatives add.

Choices made one after another multiply, but a choice of one option or another adds

There are two drinks, then two cakes for each. Each drink opens two more paths.

Because the choices happen one after the other, they multiply.

Choosing one option or the other adds the counts instead of multiplying them.

Factorials #

Every order n different things can sit in.

Arranging n different things in a row can be done in n factorial ways

Any of the 3 books can fill the first slot. Place one and 2 remain, then 1.

The exclamation mark means multiply all the way down to 1, so 5 slots give 120 ways.

There is exactly one way to arrange nothing, so zero factorial is 1.

Permutations #

Arrangements, where the order matters.

A permutation counts arrangements, so the order the things land in matters

Three medals go to eight runners, and who gets which medal matters.

8 runners can take gold, then 7 are left for silver, then 6 for bronze.

This is written nPr: multiply r factors, counting down from n.

Combinations #

Selections, where the order does not.

A combination counts selections, so rearranging the same things changes nothing

Pick a team of 3 from 8. Nobody on the team has a rank.

Every team was counted 3! = 6 times, once for each order of picking.

So divide the permutations by r factorial: $nCr=nPr/r!$nCr = nPr / r!.

Repeats and Restrictions #

Divide out the swaps you cannot see.

Repeated items are counted too many times, so divide by the arrangements of each repeat

The name Anna has two As and two Ns, so many rearrangements are identical.

Divide by the arrangements of each repeated letter: 24 ÷ 4 = 6.

Glue the tied pair into one item: 6 orders, and the pair can sit 2 ways, so 12.

Counting with Geometry #

Choosing points to make lines and triangles.

Choosing points is a combination, because a line is the same whichever end you name first

Here are 3 points on a circle: A, B and C.

Choosing 2 points from 3 gives 3 lines: AB and BA are the same line.

Choose 3 points from these 4 and you get 4 triangles. One of them is drawn here.