Combinatorics definitions Flashcards
set
A set A is a collection of objects which we call elements of A
subset
A set X is a subset of a set Y denoted X⊆Y if every element of X is also an element of Y
proper subset
X is a proper subset of Y if X⊆Y and Y⊆X
function
A function f consists of 3 things:
1) a set called the domain of f
2) a set called the codomain of f
3) a rule that associates each element a in the domain with a single element f(a) in the codomain
injective
Let f:A->B be a function, we say f is injective if for any a,a’∈A with a≠ a’ we have f(a)≠ f(a’)
equivalently, f is injective if for any a,a’∈A with f(a)=f(a’) we have a=a’
surjective
Let f:A->B be a function, we say f is surjective if for any b∈B there exists a∈A s.t. f(a)=b
equivalently, f is surjective if the image of f is B
bijective
Let f:A->B be a function, we say f is bijective if it is both injective and surjective
equivalently, f is bijective if for every b∈B there is exactly one element a∈A with f(a)=b
inverse function
Let f:A->B be a bjection. The inverse function of f is the function f⁻¹: B->A in which for each b∈B we set f⁻¹(b) to be the unique element a∈A s.t. f(a)=b
Composition
Let f:A-> Band g:B->C be functions. The composition on f and g is the function g∘f: A->C defined by (g∘f)(x) = g(f(x))
set size
For a non-negative integer n, we say that a set X has size n if there exists a bijection f:{1,2,…,n}->X.
if such n exists we say that X is finite, otherwise X is infinite.
cartesian product two sets
The cartesian product of two sets A and B is defined by AxB={(a,b): a∈A and b∈B}
cartesian product general
For each non-negative integer r the cartesian product of sets A₁,…,Aᵣ denoted Xᵢ₌₁ʳAᵢ = A₁x…xAᵣ={(x₁,…,xᵣ): xⱼ∈Aⱼ∀j∈{1,…r}
power set
The power set of A is defined by P(A) = {x:x⊆A}
So P(A) is a set whose elements are a subset of Afactorial
For any integer n≥0 we define n factorial, n!, by n!=nx(n-1)x(n-2)x…x3x2x1
(0!=1)
binomial coefficiant
The binomial coefficant of n and r also called n choose r is given by (n r) = n!/(r!(n-r)!)
