Samenvatting
Samenvatting Wiskundige Methoden (FEB21010)
Uitgebreide samenvatting van Wiskundige Methoden (econometrie EUR)
[Meer zien]Voorbeeld 2 van de 5 pagina's
Voorbeeld 2 van de 5 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
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 𝐺 = (𝑉% ∪ 𝑉( , 𝐸)
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper LeonVerweij. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €6,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 53340 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen