combinatorics cards Flashcards
pigeonhole principle
let n∈ℕ. If at least n+1 pigeons are placed in n pigeonholes, then some pigeonhole contains at least two pigeons
pigeonhole principle general
let n,k∈ℕ. If at least n pigeons are placed in k pigeonholes, the some pigeonhole contains atleast ⌈n/k⌉ pigeons
ceiling of x, ⌈ x ⌉
the smallest integer greater than or equal to x
floor of x, ⌊ x ⌋
the greatest integer less than or equal to x
⌈ x ⌉ =
⌊ - x ⌋
other ways the define the set {1,2,3,4}
EXAMPLES
{x∈ℕ: x<5}
{x-1| x∈{2,3,4,5}}
Union
AUB is the set consisting of anything in A OR anything in B
Intersection
A∩B is the set consisting of anything in A AND anything in B
Difference
A\B is the set consisting of anything in A but not in B
Complement
In context of the universal set the complement of A is defined by Aᶜ = U/A
consequences of the axiom of extension
- it doesnt matter the order of elements
- elements cannot appear in a set more than once
- There is exactly one set with no elements called the empty set {}
property of ∈
not transitive i.e. if a∈b and b∈c that doesn’t mean a∈c
subset
A is a subset of B if the set A is contained in B. A⊆B.
image of a under f
f(a)
image
the set of elements in the codomain which are mapped to
functions a and b are equal if
- equal domains
- equal codomains
- same rule
injective
different elements of the domain map to different elements in the codomain
surjective
every element of the codomain is mapped to
bijective
both injective and surjective
if f is a bijection then there is precisely…
one element of the domain s.t. f(a)=b
bijective functions are…
invertible
the inverse of a bijection is…
a bijection
A set X has size n if there exists…
a bijection f:{1,2…n}->X
distributivity of ∩ and ∪
A∩(B∪C) = (A∩B)∪(A∩C)
∩ ∪ are
associative and commutative
ordered r-tuple
a sequence of r objects which we refer to as elements or co-ordinates in a given order (a,b,c,…)
in tuples..
order matters and elements can be repeated
cartesian product
cartesian product of A and B is given by AxB {(a,b): a∈A and b∈B}
powers of sets
Aⁿ = AxAx…xA
Power set
a set whose elements are the subsets of A
choosing a possibility of one type or another
m+n posiibilities (assuming no overlap)
choosing a possiblity of each type
mn posibilities
Uniformly random choice
a choice where all outcomes are equally as likely
probability of an event where there are a finite number of possible outcomes each with a uniformly random chance of being picked
P(E) = number of outcomes for which E occurs/ total number of outcomes
binomial coefficiant of n choose n
1
binomial coefficiant of n choose n-1
n
binomial coefficiant of n choose n-2
n(n-2)/2
ways to choose r elements from a set of size n where order matters and repition is allowed
nʳ
ways to choose r elements from a set of size n where order matters and repition is not allowed
n!/(n-r)!
ways to choose r elements from a set of size n where order doesnt matter and repition is allowed
n+r-1 choose r
ways to choose r elements from a set of size n where order doesn’t matter and repition is not allowed
n choose r
permutation
A permutation of set S of size n is an ordered n-tuple in which each element of S appears once
0! =
1
If there is an overlap of sets then
use inclusion exclusion
probability of an element being chosen from a total of n elements where order matters and repetition is not allowed
(n-r)!/n!
probability of an element being chosen from a total of n elements where order matters and repetition is allowed
1/nʳ
probability of an element being chosen from a total of n elements where order doesn’t matter and repetition is allowed
no probability
probability of an element being chosen from a total of n elements where order doesnt matter and repetition is not allowed
r!(n-r)!/n!
workout the probability of certain values being chosen
- workout the outcomes that fit the condition given
- workout the total number of possible outcomes
- divide the value from 1. by the value from 2.
how many permutations are there of S? where |S|=n
n!
finding the probability for an unordered set where repetition is allowed
- work out the possible set outcomes
- pick out the ordered sets which match the condition. workout all the permutations of these sets
- divide the no. permutations of all the possible sets by the the set of possible outcomes.
binomial theorem
allows you to express a power of a sum as a sum of individual terms
if |X|≤|Y| and |Y|≤|Z| then
|X|≤|Z|
if |X|≤|Y| and |Y|≤|X| then
|X|=|Y|
for to sets we must either have
|X|≤|Y| or |Y|≤|X|
A proper subset may have the same…
cardinality as the original set
The smallest cardinality of an infinite set is…
|ℕ|
countable infite
if there exists a bijection f:ℕ->X
A set is countable if
it is finite or countably infinite
A set in uncountable if
its not finite or countably infinite
small infinite set
countably infinite stes
large infinite sets
uncountable sets
Continuum hypothesis
Does there exist a set whose cardinality is larger than |ℕ| and smaller than |ℝ|
Russels paradox
There is a contradiction by defining sets {n:n is an element in a set} and says sets must be defined like {x∈X: x satisfies this property}
graph
a structure consisting of vertices and edges where each edge links two distinct vertices and any two distinct vertices are linked by at most one edge
two graphs are equal if
they have the same set of edges and vertices
Two graphs G and H are isomorphic if
we can transform G to H by relabelling vertices.
The are the same graph
how to calculate how many labelled graphs there are with a given vertex set
- work out the edge set, E, and size of edge set |E|
2. the are 2|ᴱ| graphs with vertex set V
how to calculate how many graphs there are with n vertices up to isomorphism
- work out how many graphs there are with 0,1,…|E| edges
2. sum these to get a total number of graphs
Complement of a graph
the inverse of the graph
regular graphs
all the vertices have equal order
complete graph
has an edge between every pair of vertices
total number of edges in a complete graph
n choose 2
copy
An instance of another graph at a specific point
Walk
any order of adjacent vertices where vertices and edges can be repeated as many times as you like.
connected
a graph is connected if there is a walk through all the vertices or alternatively if there is a path from u to v in G
connected components
the subgraphs that are connected (If the graph is connected there is one connected component: the graph)
acyclic
doesn’t contain a cycle
what does deleting an edge in a cycle do to graph connectedness
nothing
What three properties imply each other for trees
- T is connected
- T is acyclic
- T has n-1 edges where n is the order of the tree
size of a closed walk in a bipartite graph
2n (even)
