Sets and Counting

Set Notation #

Unions, intersections and the universal set.

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

Read the full lesson →

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

Read the full lesson →

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

Read the full lesson →

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

Read the full lesson →

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

Read the full lesson →

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

Read the full lesson →

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

Read the full lesson →

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

Read the full lesson →

There are three drinks, then four cakes for each. Each drink opens four 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

Read the full lesson →

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

Read the full lesson →

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

Read the full lesson →

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

Read the full lesson →

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

Read the full lesson →

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.

Arrangements in a Circle #

Seating people around a round table, where turning everyone changes nothing.

Around a table only who sits next to whom counts, so turning everyone round gives the same arrangement

Read the full lesson →

Turn everyone one seat round and each person keeps both neighbors: the same arrangement. Swapping B and C makes a new one.

Each table arrangement can be turned 4 ways, so the 24 orders in a line count it 4 times: 24 ÷ 4 = 6.

Or seat A first, which fixes the turning: the other 3 then fill their seats in 3 × 2 × 1 = 6 ways.

If B and C must sit together, glue them into one item: 5 items make 4! = 24 arrangements, and the pair can sit 2 ways, so 48.

To keep B and C apart, take the 48 arrangements with them together away from all 120: that leaves 72.