Combinatorics definitions

Question 1

set

Answer 1

A set A is a collection of objects which we call elements of A

Question 2

subset

Answer 2

A set X is a subset of a set Y denoted X⊆Y if every element of X is also an element of Y

Question 3

proper subset

Answer 3

X is a proper subset of Y if X⊆Y and Y⊆X

Question 4

function

Answer 4

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

Question 5

injective

Answer 5

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’

Question 6

surjective

Answer 6

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

Question 7

bijective

Answer 7

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

Question 8

inverse function

Answer 8

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

Question 9

Composition

Answer 9

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))

Question 10

set size

Answer 10

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.

Question 11

cartesian product two sets

Answer 11

The cartesian product of two sets A and B is defined by AxB={(a,b): a∈A and b∈B}

Question 12

cartesian product general

Answer 12

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}

Question 13

power set

Answer 13

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 A

Question 14

factorial

Answer 14

For any integer n≥0 we define n factorial, n!, by n!=nx(n-1)x(n-2)x…x3x2x1
(0!=1)

Question 15

binomial coefficiant

Answer 15

The binomial coefficant of n and r also called n choose r is given by (n r) = n!/(r!(n-r)!)

Question 16

permutation

Answer 16

A permutation of a set S of size n is an ordered n-tuple in which each element of S appears once