Counting

Question 1

Are sets dependent on order?

Answer 1

No - so
{1,5,3,4,2}
is the same as {1,2,3,4,5}

Question 2

What is the cardinality of a set?

Answer 2

The number of elements that a set has

Question 3

What is the cardinality of the empty set?

Answer 3

0, denoted by an angled theta.

Question 4

What is the definition of a finite set?

Answer 4

If there is a one-to-one correspondence with another set, {1, …, n}
So if it can be numbered from 1,2 … n.

Question 5

Can countable sets be infinite or finite?

Answer 5

Both - but not all infinite sets are countable, all finite ones are.

Question 6

How can a set be countable and inifinte?

Answer 6

If there is a bijection between that set and the set of all natural numbers.

Question 7

What is the sum rule for disjoint sets?

Answer 7

(A U B) = #A + #B

Question 8

What is the generalisation of the sum rule?

Answer 8

That for task T, which can be executed in one of n1, n2 … nm ways,
the total amount of ways to execute that task are
n = (m (sigma) i = 1 ) ni

Question 9

What is the formal definition of the product rule?

Answer 9

For T1, T2, Tm tasks, executable in ni different ways,
n = (m (product) i = 1) ni

Question 10

What is the product rule for finite sets?

Answer 10

(AxB) = #A#B

Question 11

What is a subset?

Answer 11

A total overlap of sets - so if all of set A is in set B, then set A is a subset of set B.

Question 12

What is the subtraction rule?

Answer 12

Fixing the overcount present in the sum rule - #(A U B) = #A + #B - #(A∩B)
So cardinality of both sets, minus the cardinality of the intersection

Question 13

How is the subtraction rule used for larger unions? (Inclusion/exclusion)

Answer 13

Include the cardinality of odd-way intersections (e.g. third, first) and exclude the cardinality of even-way intersections (e.g. second).

Question 14

What is the formal notation for larger unions with the subtraction rule? (Inclusion/Exclusion)

Answer 14

(-1)^n-1 #(A ∩ B ∩ ….)

Question 15

What is the division rule?

Answer 15

If there are n(a) ways to do a task, but d of the ways are equivalent/identical, then there are really n = n(a)/d ways to do said task.

Question 16

What do the floor and ceiling functions do?

Answer 16

Floor rounds down to the nearest int, ceiling rounds up to the nearest int.

Question 17

What is the pigeonhole principle?

Answer 17

That if there are n items put into m boxes, n > m, then at least one box must have more than one item.

Question 18

What is the mathematical expression for the pigeonhole princp.?

Answer 18

ceiling(n/m)

Question 19

What is the proof by contradiction for the pigeonhole principle?

Answer 19

If none of the boxes have more than (ceiling(n/m) -1), then the total number of objects cannot be more than m times that. However, ceiling(x) < x + 1, so
m(ceiling(n/m)-1) < m((n/m +1)-1;
m(ceiling(n/m) - 1) < n, a contradiction as there are n items.

Question 20

What is a permutation?

Answer 20

A set of arrangements made from a set of elements, where the order is RELEVANT.
E.g. a passcode

Question 21

What is a combination?

Answer 21

A set of arrangements made from a set of elements, where the order is IRRELEVANT.
E.g. a fruit bowl

Question 22

What are the sets of permutations and combinations from flipping a coin twice?

Answer 22

Combinations: {HH, HT, TT}
Permutations: {HH, TH, HT, TT}

Question 23

What is nCr?

Answer 23

The number of subsets with r elements selected from a set with n elements.

Question 24

What is choosing r from n the same as?

Answer 24

Choosing r from n is the same as choosing (n-r) from n.

Question 25

What is the formula for permutations with repitition?

Answer 25

n^r

Question 26

What is the formula for permutations without rep?

Answer 26

n!/(n-r)!

Question 27

What is the formula for combinations with rep?

Answer 27

(r+n-1)! / r!(n-1)!

Question 28

What is the formula for combinations without rep?

Answer 28

n! / r!(n-r)!

Question 29

What is the magnitude of permutations, combinations, and repititions?

Answer 29

There are more permutations than combinations, and more perms/combs with repititions than without.

Question 30

What is Pascal’s identity?

Answer 30

(n) = (n - 1) + (n-1)
(r) = (r - 1) + (r)
Where r <= n

Question 31

What is a derangement?

Answer 31

A permutation that leaves no objects in their original position

Question 32

How do you calculate !n?

Answer 32

!n = n! - n!/1! + n!/2! - n!/3!…..

Question 33

What is !n approximately equal to?

Answer 33

!n = n!/e, always correct if you round it.