combinatorics cards Flashcards by Lucy Clare

pigeonhole principle

let n∈ℕ. If at least n+1 pigeons are placed in n pigeonholes, then some pigeonhole contains at least two pigeons

How well did you know this?

Not at all

Perfectly

pigeonhole principle general

let n,k∈ℕ. If at least n pigeons are placed in k pigeonholes, the some pigeonhole contains atleast ⌈n/k⌉ pigeons

How well did you know this?

Not at all

Perfectly

ceiling of x, ⌈ x ⌉

the smallest integer greater than or equal to x

How well did you know this?

Not at all

Perfectly

floor of x, ⌊ x ⌋

the greatest integer less than or equal to x

How well did you know this?

Not at all

Perfectly

⌈ x ⌉ =

⌊ - x ⌋

How well did you know this?

Not at all

Perfectly

other ways the define the set {1,2,3,4}

EXAMPLES
{x∈ℕ: x<5}
{x-1| x∈{2,3,4,5}}

How well did you know this?

Not at all

Perfectly

Union

AUB is the set consisting of anything in A OR anything in B

How well did you know this?

Not at all

Perfectly

Intersection

A∩B is the set consisting of anything in A AND anything in B

How well did you know this?

Not at all

Perfectly

Difference

A\B is the set consisting of anything in A but not in B

How well did you know this?

Not at all

Perfectly

Complement

In context of the universal set the complement of A is defined by Aᶜ = U/A

How well did you know this?

Not at all

Perfectly

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 {}

How well did you know this?

Not at all

Perfectly

property of ∈

not transitive i.e. if a∈b and b∈c that doesn’t mean a∈c

How well did you know this?

Not at all

Perfectly

subset

A is a subset of B if the set A is contained in B. A⊆B.

How well did you know this?

Not at all

Perfectly

image of a under f

f(a)

How well did you know this?

Not at all

Perfectly

image

the set of elements in the codomain which are mapped to

How well did you know this?

Not at all

Perfectly

functions a and b are equal if

equal domains
equal codomains
same rule

How well did you know this?

Not at all

Perfectly

injective

different elements of the domain map to different elements in the codomain

How well did you know this?

Not at all

Perfectly

surjective

every element of the codomain is mapped to

How well did you know this?

Not at all

Perfectly

bijective

both injective and surjective

How well did you know this?

Not at all

Perfectly

if f is a bijection then there is precisely…

one element of the domain s.t. f(a)=b

How well did you know this?

Not at all

Perfectly

bijective functions are…

invertible

How well did you know this?

Not at all

Perfectly

the inverse of a bijection is…

a bijection

How well did you know this?

Not at all

Perfectly

A set X has size n if there exists…

a bijection f:{1,2…n}->X

How well did you know this?

Not at all

Perfectly

distributivity of ∩ and ∪

A∩(B∪C) = (A∩B)∪(A∩C)

How well did you know this?

Not at all

Perfectly

∩ ∪ 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

binomial coefficiant of n choose n-1

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! =

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

1. workout the outcomes that fit the condition given 2. workout the total number of possible outcomes 3. divide the value from 1. by the value from 2.

how many permutations are there of S? where |S|=n

finding the probability for an unordered set where repetition is allowed

1. work out the possible set outcomes 2. pick out the ordered sets which match the condition. workout all the permutations of these sets 3. 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

how to calculate how many graphs there are with n vertices up to isomorphism

1. 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

1. T is connected 2. T is acyclic 3. T has n-1 edges where n is the order of the tree

size of a closed walk in a bipartite graph

2n (even)