Summary
Summary of Mathematical Methods (FEB21010X)
- Course
- Institution
Comprehensive summary of Mathematical Methods (Econometrics EUR)
[Show more]
Seller
Follow
LeonVerweij
Reviews received
Content preview
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 𝐺 = (𝑉% ∪ 𝑉( , 𝐸)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller LeonVerweij. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
71498 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now
Recently viewed by you
