-
Notifications
You must be signed in to change notification settings - Fork 0
/
001-math-basics.qmd
162 lines (118 loc) · 5.58 KB
/
001-math-basics.qmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
# Math Basics
# Useful
* [Wikipedia: Glossary of mathematical symbols](https://en.wikipedia.org/wiki/Glossary_of_mathematical_symbols)
# Exponentiation
Rules
* $a^m a^n = a^{m+n}$
* $\frac{a^m}{a^n} = a^{m-n}$
* $(a^m)^n = a^{mn}$
* $a^n b^n = (ab)^n$
* $\frac{a^n}{b^n} = \left(\frac{a}{b}\right)^n$
Special cases
* $a^1 = a$
* $a^0 = 1, \quad a \neq 0$
* $aa^n = a^{n+1}$
* $1^n = 1$
* $0^n = 0, \quad n > 0$
* $a^{-n} = \frac{1}{a^n}$
# Logarithm
$y = \log_ax \quad \Leftrightarrow \quad a^y = x$
Rules
* $\log(uv) = \log u + \log v$
* $\log\left(\frac{u}{v}\right) = \log u - \log v$
* $\log\left(\frac{1}{v}\right) = -\log v$
* $\log(u^r) = r \log u$
Change of base
$\log_a x = \frac{\log_b x}{\log_b a}$
# Set Theory
| Notation | Meaning | Example | Latex |
|----------|---------|-----------|--------|
| **Constants** |
| $\emptyset$ | Empty set | $|\emptyset|=0$ | `\emptyset` |
| $\mathbb{N}$ | Natural numbers | $1 \in \mathbb{N}$ | `\mathbb{N}` |
| $\mathbb{Z}$ | Integers | If $m, n \in \mathbb{Z}$, then $m+n, mn \in \mathbb{Z}$ | `\mathbb{Z}` |
| $\mathbb{Q}$ | Rational numbers | $\pi \notin \mathbb{Q}$ | `\mathbb{Q}` |
| $\mathbb{R}$ | Real numbers | $e \in \mathbb{R}$ | `\mathbb{R}` |
| $\mathbb{C}$ | Complex numbers | $\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$ | `\mathbb{C}` |
| **General** |
| $A$ | Sets | $A \subseteq B \cup C$ | |
| $\{\}$ | Indicator for Sets | $\{5, e, \pi, 1\}$ | `\{ \}` |
| $|,:$ | [Set Builder](https://en.wikipedia.org/wiki/Set-builder_notation#Sets_defined_by_a_predicate) ('such that') | $\{x^2: x \in \mathbb{Z}\}$, $\{y \in \mathbb{Z} \mid y = x^2 \text{ for some } x \in \mathbb{Z}\}$ | `\mid`, `:`|
| **Operators** |
| $A^\complement$ | Complement ('not') | | `A^\complement` |
| $\cap$ | Intersection ('and') | $A \cap B$ | `\cap` |
| $\cup$ | Union ('or') | $A \cup B$ | `\cup` |
| **Relation** |
| $\in$, $\notin$ | Is (not) member of | $x \in A$ | `\in`, `\notin` |
| $\ni$, $\not\ni$ | Owns (not) | $A \ni x$ | `\ni`, `\notin` |
| $\subseteq$, $\not\subseteq$ | Is (not) subset of | $A \subseteq B$ | `\subseteq`, `\not\subseteq` |
| $\supseteq$, $\not\supseteq$ | Is (not) superset of | $A \supseteq B$ | `\supseteq`, `\not\supseteq` |
| $\subset$, $\not\subset$ | Is (not) proper subset of | $A \subset B$ | `\subset`, `\not\subset` |
| $\supset$, $\not\supset$ | Is (not) proper superset of | $B \supset A$ | `\supset`, `\not\supset` |
```{r, set-theory1, echo=FALSE, fig.cap='Venn diagrams', fig.pos="tb"}
knitr::include_graphics('figures/03_inkscape/set_theory/set_theory.png')
```
Further
* [Latex Wiki](https://oeis.org/wiki/List_of_LaTeX_mathematical_symbols)
* [Mathvault](https://mathvault.ca/hub/higher-math/math-symbols/set-theory-symbols/)
Laws of set theory
* Commutative Laws
- $A \cup B = B \cup A$
- $A \cap B = B \cap A$
* Associative Laws
- $(A \cup B) \cup C = A \cup (B \cup C)$
- $(A \cap B) \cap C = A \cap (B \cap C)$
* Distributive Laws
- $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$
- $(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$
* De Morgan's laws
- $(A \cap B)^\complement = A^\complement \cup B^\complement$
- $(A \cup B)^\complement = A^\complement \cap B^\complement$
Terms
* Disjoint
- $A$ and $B$ are called disjoint if $A \cap B = \emptyset$
# Discrete Mathematics
**Factorial**
\begin{align*}
0! &= 1\\
n! &= 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (n-1) \cdot n
\end{align*}
**Binomial coefficient**
$$
{n \choose k} = \frac{n!}{k!(n-k)!}
$$
# Combinatorics
Draw $k$ balls out of an urn with $n$ balls. Number of possible samples
| | With replacement | Without replacement |
|-----------------|---------------------|---------------------|
| regard order | $n^k$ | $n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot(n-k+1) = \frac{n!}{(n-k)!}$ |
| disregard order | ${n+k-1 \choose k}$ | ${n \choose k}$ |
* $\Omega$ is a set with $n$ elements
- Number of ways to arrange $k$ elements out of $\Omega$
+ $n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot(n-k+1) = \frac{n!}{(n-k)!}$
- Number of ways to arrange $n$ elements
+ $n!$
- Number of combinations (subsets) of $\Omega$ with $k$ elements
+ ${n \choose k}$
- Number of ways, to split $\Omega$ into $r$ disjoint sets with $k_1, k_2, \ldots, k_r$ Elments (assuming $k_1 + k_2 + \ldots + k_r = n$)
+ $\frac{n!}{k_1! \cdot k_2! \cdot \ldots \cdot k_r!}$
More general possible cases for combinatorial problems
* [Twelvefold Way](https://www.johndcook.com/TwelvefoldWay.pdf)
* [SO: Implementation of permutation/combination in R](https://stackoverflow.com/a/47983855/6152316)
# Inequalities
Inequalities can be transformed by applying any **monotonic** transformation $f(x)$ to both sides of the inequality. The inequality symbol has to be **reversed** if the function $f(x)$ is monotonically decreasing. Details [Wikipedia](https://en.wikipedia.org/wiki/Inequality_(mathematics)#Properties_on_the_number_line)
* monotonically increasing
- Multiply by positive factor
- Add/subtract number ($f(x) = x + a$)
- $f(x) = \exp(x)$, $f(x) = \log(x)$, ...
* monotonically decreasing
- Multiply by negative factor
- $f(x) = x^{-1}$, ...
# Optimization
* Sometimes solution can be directly calcualted
- Closed form solution
- Non-iterative solution
- Explicit solution
- Direct solution
- Analytic solution
* Otherwise we need numerical optimization to iteratively find a solution