Counting Flashcards
Are sets dependent on order?
No - so
{1,5,3,4,2}
is the same as {1,2,3,4,5}
What is the cardinality of a set?
The number of elements that a set has
What is the cardinality of the empty set?
0, denoted by an angled theta.
What is the definition of a finite set?
If there is a one-to-one correspondence with another set, {1, …, n}
So if it can be numbered from 1,2 … n.
Can countable sets be infinite or finite?
Both - but not all infinite sets are countable, all finite ones are.
How can a set be countable and inifinte?
If there is a bijection between that set and the set of all natural numbers.
What is the sum rule for disjoint sets?
(A U B) = #A + #B
What is the generalisation of the sum rule?
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
What is the formal definition of the product rule?
For T1, T2, Tm tasks, executable in ni different ways,
n = (m (product) i = 1) ni
What is the product rule for finite sets?
(AxB) = #A#B
What is a subset?
A total overlap of sets - so if all of set A is in set B, then set A is a subset of set B.
What is the subtraction rule?
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
How is the subtraction rule used for larger unions? (Inclusion/exclusion)
Include the cardinality of odd-way intersections (e.g. third, first) and exclude the cardinality of even-way intersections (e.g. second).
What is the formal notation for larger unions with the subtraction rule? (Inclusion/Exclusion)
(-1)^n-1 #(A ∩ B ∩ ….)
What is the division rule?
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.
What do the floor and ceiling functions do?
Floor rounds down to the nearest int, ceiling rounds up to the nearest int.
What is the pigeonhole principle?
That if there are n items put into m boxes, n > m, then at least one box must have more than one item.
What is the mathematical expression for the pigeonhole princp.?
ceiling(n/m)
What is the proof by contradiction for the pigeonhole principle?
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.
What is a permutation?
A set of arrangements made from a set of elements, where the order is RELEVANT.
E.g. a passcode
What is a combination?
A set of arrangements made from a set of elements, where the order is IRRELEVANT.
E.g. a fruit bowl
What are the sets of permutations and combinations from flipping a coin twice?
Combinations: {HH, HT, TT}
Permutations: {HH, TH, HT, TT}
What is nCr?
The number of subsets with r elements selected from a set with n elements.
What is choosing r from n the same as?
Choosing r from n is the same as choosing (n-r) from n.
What is the formula for permutations with repitition?
n^r
What is the formula for permutations without rep?
n!/(n-r)!
What is the formula for combinations with rep?
(r+n-1)! / r!(n-1)!
What is the formula for combinations without rep?
n! / r!(n-r)!
What is the magnitude of permutations, combinations, and repititions?
There are more permutations than combinations, and more perms/combs with repititions than without.
What is Pascal’s identity?
(n) = (n - 1) + (n-1)
(r) = (r - 1) + (r)
Where r <= n
What is a derangement?
A permutation that leaves no objects in their original position
How do you calculate !n?
!n = n! - n!/1! + n!/2! - n!/3!…..
What is !n approximately equal to?
!n = n!/e, always correct if you round it.
