Combinatorics
𝑘 from 𝑛 Without repetition With repetition
𝑘-permutation from n
𝑛! 𝑘-permutation with repetition from 𝑛
With order
𝑃(𝑛, 𝑘) = 𝑛!
(𝑛 − 𝑘)!
𝑘-combination from 𝑛 𝑘-combination with repetition from 𝑛
Without order 𝑛 𝑛! 𝑛+𝑘−1 (𝑛 + 𝑘 − 1)!
* + = |𝒫(𝑁" , 𝑘)| = / 2=
𝑘 𝑘! (𝑛 − 𝑘)! 𝑘 (𝑛 − 1)! 𝑘!
One-to-one rule
Let 𝐴 and 𝐵 be finite sets. The number of elements in 𝐴 and 𝐵 is equal (|𝐴| = |𝐵|) ⟺ there is a
one-to-one correspondence (bijection) between 𝐴 and 𝐵
Rule of sum
If 𝐴 and 𝐵 are finite, disjoint sets, then |𝐴 ∪ 𝐵| = |𝐴| + |𝐵|
In general, if 𝐴 ∩ 𝐵 ≠ ∅, then |𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵|
Rule of product
If 𝐴 and 𝐵 are finite sets, then |𝐴 × 𝐵| = |𝐴| ∙ |𝐵|
Rule of difference
Let 𝐴 and 𝐵 be sets, then we define their difference as 𝐴\𝐵 = {𝑥 ∈ 𝐴: 𝑥 ∉ 𝐵)
If 𝐴 and 𝐵 are finite sets and 𝐵 ⊆ 𝐴, then |𝐴\𝐵| = |𝐴| − |𝐵|
Power set
Let 𝑋 be a finite set, we define 𝒫(𝑋) = {𝐴: 𝐴 ⊆ 𝑋} as the set cointaining all subsets of 𝑋
For 𝑘 ≥ 0, we define 𝒫(𝑋, 𝑘) = {𝐴: 𝐴 ⊆ 𝑋; |𝐴| = 𝑘}
Combinations without repetitions
Equals the problem to select 𝑘 elements from a set with 𝑛 elements without repetion and order,
select a subset of size 𝑘 from a set with 𝑛 elements, select an element in the set 𝒫(𝑁" , 𝑘)
Combinatorial Theorems
I. Complementarity: for 𝑛, 𝑘 ∈ ℕ with 𝑘 ≤ 𝑛, it holds that J"!K = J"#!"
K
II. Pascal’s identity: for 𝑛, 𝑘 ∈ ℕ with 1 ≤ 𝑘 ≤ 𝑛, it holds that J ! K = J"!K + J!#%
"$% "
K
Newton’s binomial theorem
Let 𝑛 ∈ ℕ and 𝑥, 𝑦 ∈ ℝ, then (𝑥 + 𝑦)" = ∑"&'%J"!K 𝑥 ! 𝑦 "#!
Combinatorial proof
0. Make a drawing to understand the equality
1. Write the left-hand side as the number of elements in a set
2. Write the right-hand side as the number of elements in a set
3. Show that the number of elements in both sets is equal by defining a one-to-one
correspondence, so for example by making a function that goes from the left-hand side to
the right-hand side and its inverse
Multinomial numbers
The number of k-permutations with repetition from 𝑛, of type 𝑡% , 𝑡( , … , 𝑡" equals
!!
*) ,) !,…,) + = ) !∙) !∙…∙) ! , with 𝑡% + 𝑡( + ⋯ + 𝑡" = 𝑘
! " # ! " #
k-combinations with repetition from n
Denote 𝑧& as the number of stars in the 𝑖th group. Then this can be viewed as a solution of the
equation 𝑧% + 𝑧( + ⋯ + 𝑧" = 𝑘 with 𝑧 ∈ {0,1,2 … }. The number of solutions is then J"$!#%!
K
, Graph Theory
Definition of a graph
A graph consists of two sets: a non-empty finite set 𝑉 of vertices and a set 𝐸 of edges, each edge
is a set of two vertices from 𝑉. The graph is denoted by 𝐺 = (𝑉, 𝐸)
Graph isomorphisms
Consider two graphs 𝐺 = (𝑉, 𝐸) and 𝐻 = (𝑊, 𝐹). A graph isomorphism 𝑓 from 𝐺 to 𝐻, is a
function 𝑓, such that 𝑓: 𝑉 → 𝑊 is a one-to-one relation and {𝑣% , 𝑣( } ∈ 𝐸 ⟺ {𝑓(𝑣% ), 𝑓(𝑣( )} ∈ 𝐹
Terminology
Consider a graph 𝐺 = (𝑉, 𝐸)
- Let 𝑒 = {𝑢, 𝑣} ∈ 𝐸 be an edge, we say that the edge 𝑒 connects 𝑢 and 𝑣, that 𝑒 is incident to
𝑢 and 𝑣 and that 𝑢 and 𝑣 are neighbors
- The degree of 𝑣 ∈ 𝑉 is the number of edges incident to 𝑣, 𝑑(𝑣) is the degree of 𝑣
- If a vertex 𝑣 ∈ 𝑉 has degree 1, then 𝑣 is and endpoint
- Let 𝐻 = (𝑊, 𝐹) be another graph, then 𝐻 is a subgraph of 𝐺 (𝐻 ⊆ 𝐺) if 𝑊 ⊆ 𝑉 and 𝐹 ⊆ 𝐸
First theorem on graph theory
Consider a graph 𝐺 = (𝑉, 𝐸), then ∑.∈0 𝑑(𝑣) = 2|𝐸|
Walking in a graph
A walk in a graph 𝐺 = (𝑉, 𝐸) is an alternating sequence 𝑣1 , 𝑒% , 𝑣% , 𝑒( , 𝑣( , … , 𝑒! , 𝑣! of vertices and
edges, such that edge 𝑒& is incident to 𝑣&#% and 𝑣& , for all 1 ≤ 𝑖 ≤ 𝑘. The number of edges in the
walk is the length of the walk. 𝑣1 is the start point of the walk, 𝑣! the end point. If 𝑣1 = 𝑣! , then
the walk is closed, otherwise it is open. The walk can also be denoted as 𝑣1 → 𝑣% → ⋯ → 𝑣!
Special walks
Open Closed and non-trivial
Contains each edge at most once Trail (route) Circuit
Contains each vertex and each edge at most one Path (pad) Cycle
Walk and path
Let 𝐺 = (𝑉, 𝐸) be a graph and 𝑢, 𝑣 be vertices in 𝑉. Every 𝑢, 𝑣-walk contain a 𝑢, 𝑣-path
Walk and cycle
Let 𝐺 = (𝑉, 𝐸) be a graph. A closed walk in 𝐺 of odd length contains a cycle of odd length
Distance in a graph
The distance 𝑑(𝑢, 𝑣) between two vertices 𝑢, 𝑣 ∈ 𝑉 in a graph 𝐺 = (𝑉, 𝐸) is the length of the
shortest 𝑢, 𝑣-path. If there is no path from 𝑢 to 𝑣, then 𝑑(𝑢, 𝑣) if infinite
The distance in a graph satisfies the triangle inequality: 𝑑(𝑢, 𝑣) ≤ 𝑑(𝑢, 𝑤) + 𝑑(𝑤, 𝑣)
Special graphs
The complete graph 𝐾" is the graph with all possible edges, the path 𝑃" is a graph that satisfies
the properties op a path, the cycle 𝐶" is a graph that satisfies the properties op a cycle
Connected graph
A graph 𝐺 is connected if for each pair of vertices 𝑢, 𝑣, there is a 𝑢, 𝑣-path in 𝐺
If a graph is not connected, it contains several connected components
Theorem connected graphs
Let 𝐺 = (𝑉, 𝐸) be a graph. Define the complement of 𝐺 as the graph 𝐺̅ (𝑉, 𝐸f ) that has the same
set of vertices, but contains all edges 𝑒 that are not in 𝐺. Then, 𝐺 is connected and/or 𝐺̅ is
connected
Spanning subgraph
Let 𝐺 = (𝑉, 𝐸) be a graph and let 𝐻 = (𝑊, 𝐹) be a subgraph of 𝐺. 𝐻 is spanning if 𝑊 = 𝑉
Bipartite graphs
A graph is bipartite if its vertices can be split into two parts. Splitting means that edges are from
the first part to the second part, and not within a part itself.
A bipartite graph is denoted as 𝐺 = (𝑉% ∪ 𝑉( , 𝐸)
𝑘 from 𝑛 Without repetition With repetition
𝑘-permutation from n
𝑛! 𝑘-permutation with repetition from 𝑛
With order
𝑃(𝑛, 𝑘) = 𝑛!
(𝑛 − 𝑘)!
𝑘-combination from 𝑛 𝑘-combination with repetition from 𝑛
Without order 𝑛 𝑛! 𝑛+𝑘−1 (𝑛 + 𝑘 − 1)!
* + = |𝒫(𝑁" , 𝑘)| = / 2=
𝑘 𝑘! (𝑛 − 𝑘)! 𝑘 (𝑛 − 1)! 𝑘!
One-to-one rule
Let 𝐴 and 𝐵 be finite sets. The number of elements in 𝐴 and 𝐵 is equal (|𝐴| = |𝐵|) ⟺ there is a
one-to-one correspondence (bijection) between 𝐴 and 𝐵
Rule of sum
If 𝐴 and 𝐵 are finite, disjoint sets, then |𝐴 ∪ 𝐵| = |𝐴| + |𝐵|
In general, if 𝐴 ∩ 𝐵 ≠ ∅, then |𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵|
Rule of product
If 𝐴 and 𝐵 are finite sets, then |𝐴 × 𝐵| = |𝐴| ∙ |𝐵|
Rule of difference
Let 𝐴 and 𝐵 be sets, then we define their difference as 𝐴\𝐵 = {𝑥 ∈ 𝐴: 𝑥 ∉ 𝐵)
If 𝐴 and 𝐵 are finite sets and 𝐵 ⊆ 𝐴, then |𝐴\𝐵| = |𝐴| − |𝐵|
Power set
Let 𝑋 be a finite set, we define 𝒫(𝑋) = {𝐴: 𝐴 ⊆ 𝑋} as the set cointaining all subsets of 𝑋
For 𝑘 ≥ 0, we define 𝒫(𝑋, 𝑘) = {𝐴: 𝐴 ⊆ 𝑋; |𝐴| = 𝑘}
Combinations without repetitions
Equals the problem to select 𝑘 elements from a set with 𝑛 elements without repetion and order,
select a subset of size 𝑘 from a set with 𝑛 elements, select an element in the set 𝒫(𝑁" , 𝑘)
Combinatorial Theorems
I. Complementarity: for 𝑛, 𝑘 ∈ ℕ with 𝑘 ≤ 𝑛, it holds that J"!K = J"#!"
K
II. Pascal’s identity: for 𝑛, 𝑘 ∈ ℕ with 1 ≤ 𝑘 ≤ 𝑛, it holds that J ! K = J"!K + J!#%
"$% "
K
Newton’s binomial theorem
Let 𝑛 ∈ ℕ and 𝑥, 𝑦 ∈ ℝ, then (𝑥 + 𝑦)" = ∑"&'%J"!K 𝑥 ! 𝑦 "#!
Combinatorial proof
0. Make a drawing to understand the equality
1. Write the left-hand side as the number of elements in a set
2. Write the right-hand side as the number of elements in a set
3. Show that the number of elements in both sets is equal by defining a one-to-one
correspondence, so for example by making a function that goes from the left-hand side to
the right-hand side and its inverse
Multinomial numbers
The number of k-permutations with repetition from 𝑛, of type 𝑡% , 𝑡( , … , 𝑡" equals
!!
*) ,) !,…,) + = ) !∙) !∙…∙) ! , with 𝑡% + 𝑡( + ⋯ + 𝑡" = 𝑘
! " # ! " #
k-combinations with repetition from n
Denote 𝑧& as the number of stars in the 𝑖th group. Then this can be viewed as a solution of the
equation 𝑧% + 𝑧( + ⋯ + 𝑧" = 𝑘 with 𝑧 ∈ {0,1,2 … }. The number of solutions is then J"$!#%!
K
, Graph Theory
Definition of a graph
A graph consists of two sets: a non-empty finite set 𝑉 of vertices and a set 𝐸 of edges, each edge
is a set of two vertices from 𝑉. The graph is denoted by 𝐺 = (𝑉, 𝐸)
Graph isomorphisms
Consider two graphs 𝐺 = (𝑉, 𝐸) and 𝐻 = (𝑊, 𝐹). A graph isomorphism 𝑓 from 𝐺 to 𝐻, is a
function 𝑓, such that 𝑓: 𝑉 → 𝑊 is a one-to-one relation and {𝑣% , 𝑣( } ∈ 𝐸 ⟺ {𝑓(𝑣% ), 𝑓(𝑣( )} ∈ 𝐹
Terminology
Consider a graph 𝐺 = (𝑉, 𝐸)
- Let 𝑒 = {𝑢, 𝑣} ∈ 𝐸 be an edge, we say that the edge 𝑒 connects 𝑢 and 𝑣, that 𝑒 is incident to
𝑢 and 𝑣 and that 𝑢 and 𝑣 are neighbors
- The degree of 𝑣 ∈ 𝑉 is the number of edges incident to 𝑣, 𝑑(𝑣) is the degree of 𝑣
- If a vertex 𝑣 ∈ 𝑉 has degree 1, then 𝑣 is and endpoint
- Let 𝐻 = (𝑊, 𝐹) be another graph, then 𝐻 is a subgraph of 𝐺 (𝐻 ⊆ 𝐺) if 𝑊 ⊆ 𝑉 and 𝐹 ⊆ 𝐸
First theorem on graph theory
Consider a graph 𝐺 = (𝑉, 𝐸), then ∑.∈0 𝑑(𝑣) = 2|𝐸|
Walking in a graph
A walk in a graph 𝐺 = (𝑉, 𝐸) is an alternating sequence 𝑣1 , 𝑒% , 𝑣% , 𝑒( , 𝑣( , … , 𝑒! , 𝑣! of vertices and
edges, such that edge 𝑒& is incident to 𝑣&#% and 𝑣& , for all 1 ≤ 𝑖 ≤ 𝑘. The number of edges in the
walk is the length of the walk. 𝑣1 is the start point of the walk, 𝑣! the end point. If 𝑣1 = 𝑣! , then
the walk is closed, otherwise it is open. The walk can also be denoted as 𝑣1 → 𝑣% → ⋯ → 𝑣!
Special walks
Open Closed and non-trivial
Contains each edge at most once Trail (route) Circuit
Contains each vertex and each edge at most one Path (pad) Cycle
Walk and path
Let 𝐺 = (𝑉, 𝐸) be a graph and 𝑢, 𝑣 be vertices in 𝑉. Every 𝑢, 𝑣-walk contain a 𝑢, 𝑣-path
Walk and cycle
Let 𝐺 = (𝑉, 𝐸) be a graph. A closed walk in 𝐺 of odd length contains a cycle of odd length
Distance in a graph
The distance 𝑑(𝑢, 𝑣) between two vertices 𝑢, 𝑣 ∈ 𝑉 in a graph 𝐺 = (𝑉, 𝐸) is the length of the
shortest 𝑢, 𝑣-path. If there is no path from 𝑢 to 𝑣, then 𝑑(𝑢, 𝑣) if infinite
The distance in a graph satisfies the triangle inequality: 𝑑(𝑢, 𝑣) ≤ 𝑑(𝑢, 𝑤) + 𝑑(𝑤, 𝑣)
Special graphs
The complete graph 𝐾" is the graph with all possible edges, the path 𝑃" is a graph that satisfies
the properties op a path, the cycle 𝐶" is a graph that satisfies the properties op a cycle
Connected graph
A graph 𝐺 is connected if for each pair of vertices 𝑢, 𝑣, there is a 𝑢, 𝑣-path in 𝐺
If a graph is not connected, it contains several connected components
Theorem connected graphs
Let 𝐺 = (𝑉, 𝐸) be a graph. Define the complement of 𝐺 as the graph 𝐺̅ (𝑉, 𝐸f ) that has the same
set of vertices, but contains all edges 𝑒 that are not in 𝐺. Then, 𝐺 is connected and/or 𝐺̅ is
connected
Spanning subgraph
Let 𝐺 = (𝑉, 𝐸) be a graph and let 𝐻 = (𝑊, 𝐹) be a subgraph of 𝐺. 𝐻 is spanning if 𝑊 = 𝑉
Bipartite graphs
A graph is bipartite if its vertices can be split into two parts. Splitting means that edges are from
the first part to the second part, and not within a part itself.
A bipartite graph is denoted as 𝐺 = (𝑉% ∪ 𝑉( , 𝐸)
