Kihagyás

6. előadás

\(\mathbb{C}\)

  • algebrai alak - \(a + bi\)
  • trigonometrikus alak - \(r(\cos \theta + i \sin \theta)\)

1. állítás

Ha \(z \neq 0 \ z = r(\cos \varphi + i \sin \varphi) \quad n \in \N^+\)

azok a \(w \in \mathbb{C}\) értékek, amelyre \(w^k=z\), a következők (n db):

\(w=\sqrt[n]r\cdot(\cos\frac{\varphi+2k\pi}{n}+i\sin\frac{\varphi+2k\pi}{n})\)

\[ k = 0,1,2,\ldots,n-1 \]

Bizonyítás:

Ha \(w^n=z\), és \(w\) trigonometrikus alakja: \(w=s(\cos \alpha + i \sin \alpha)\)

\(w^n~=~s^n(\cos n\alpha + i \sin n\alpha)~=~r(\cos \varphi + i \sin \varphi)~=~z \qquad \Longleftrightarrow \begin{cases}s^n~=~r \\ n \alpha = \varphi + 2k \pi \quad \text{, ahol } k \in \Z \end{cases}\)

\(\alpha = \frac{\varphi + 2k \pi}{n} \qquad \forall k \in \Z\)

De ha \(k'=k+n \quad\Longrightarrow\quad\alpha = \frac{\varphi + 2k \pi}{n} \qquad \alpha' = \frac{\varphi + 2k' \pi}{n} (\text{Ugyanazt a }w\text{-t adja})\)

Például:

\(w^3 = 1 = 1\cdot(\cos 0 + i \sin 0)\)

  1. \(\sqrt[3]{1}\cdot(\cos \frac{0}{3} + i \sin \frac{0}{3}) = 1\)
  2. \(\sqrt[3]{1}\cdot(\cos \frac{2\pi}{3} + i \sin \frac{2\pi}{3}) = 1\)
  3. \(\sqrt[3]{1}\cdot(\cos \frac{4\pi}{3} + i \sin \frac{4\pi}{3}) = 1\)

Definíció: n-edik egységgyök

  • Azok a \(w \in \mathbb{C}\) számok, melyekre \(w^n=1\)
    • \(i\): \(4\)-edik egységgyök
      • \(i^4=(i^2)^2=(-1)^2=1\)
    • \(-i\) is: \((-1)^4=1^2=1\)
    • \(1\) is
    • \(-1\)

Gyök

Állítás: n-edik egységgyökök

\(w_k = \cos \frac{2k\pi}{n}+i\sin\frac{2k\pi}{n} \quad k = 0, 1, 2, \dots, n-1\)

3. Állítás

Ha \(z\)-nek ismerjük egy \(n\)-edik gyökét: \(v\)

\(v^n=z\), akkor a többi n-edik gyöke:

Bizonyítás:

\((v\cdot w_k)^n=v^n\cdot w_k^n=z\cdot 1 = z\)

Következtetés:

\(\forall z \in \mathbb{C}\backslash \{0\}\) n-edik gyökei szabályos n-szög.

Egységgyök rendje

Egy \(w\) egységgyök rendje: a legkisebb \(n \in \N^+\), melyre \(w^n=1\)

Például:

\(i\) rendje 4 (\(i^4 = 1\))

Primitív egységgyök

Egy \(n\)-edik egységgyök Primitív \(n\)-edik egységgyök, ha a rendje \(n\)

Az alábbiak ekvivalensek egy n-edik egységgyökre

  • \(\varepsilon\) primitív n-edik egységgyök
  • \(\varepsilon\) hatványai az összes \(n\)-edik egységgyököt előállítják
  • \(\varepsilon^0,\varepsilon^1,\dots,\varepsilon{n-1}\) mind különböző

Bizonyítás:

  • c) \(\Rightarrow\) b)
    • \((e^k)^n=(e^n)^k=1\), tehát \(e^k\) is n-edik egységgyökök, és ha mind különbözők, akkor megvan mind az \(n\).
  • b) \(\Rightarrow\) c)
    • ha lenne két azonos hatvány: \(0 \leq i < j \leq n-1\)
    • \(\varepsilon^i=\varepsilon^j \Rightarrow \varepsilon^{j-i}=1=\varepsilon^0 \Rightarrow \varepsilon^0,\varepsilon^1,\varepsilon^2,\dots,\varepsilon^{j-i}\) \(j-i\) db egységgyök áll elő
  • a) \(\Leftarrow\) c)
    • Ha az első \(\varepsilon^0, \varepsilon^1, \dots, \varepsilon^{n-1}\) mind különbözők, akkor
      • \(\varepsilon^1 \neq \varepsilon^0=1\)
      • \(\varepsilon^2 \neq 1\)
      • \(\varepsilon^3 \neq 1\)
      • stb...
      • Akkor, \(n\) a legkisebb pozitív kitevő
  • a) \(\Rightarrow\) c)
    • Ha nem lenne mind különböző: \(0 \leq i < j \leq n-1\)
    • \(\varepsilon^i=\varepsilon^j \Rightarrow \varepsilon^{j-i}=1\)

I am confusion

Kombinatorika

Leszámlálások

Alapelvek

  • Ha \(A\) és \(B\) diszjunkt, véges halmazok (\(A \cap B = \varnothing\))
    • akkor \(|A \cup B| = |A| + |B|\)
  • Ha \(A\) és \(B\) véges halmaz
    • akkor \(|A \times B| = |A|\cdot|B|\)

Kombinatorika példa

Hány 3 betűs sorozat képezhető az A, B, C betűkből, ha

  1. az A betű legalább 2-szer forduljon elő
  2. mindegyiknek szerepelnie kell

Kombinatorika példa - Első

Két eset:

  • Pont 2-szer fordul elő: "AA?", "A?A", "?AA" \(\Rightarrow\) (6 eset)
  • 3-szor fordul elő: AAA \(\Rightarrow\) 1 eset

Kombinatorika példa - Második

Első pozíció: 3-féle

Második pozíció: 2-féle (abból, ami maradt)

Harmadik pozíció: adott

Tehénszabály: Lábak száma = tehenek száma \(\times\) átlagos tehénlábszám

Skatulyaelv (pigeonhole principle): Ha \(n\) márka nélküli tárolóeszközbe \(>n\) dolgot teszek, akkor lesz olyan tárolóeszköz, melybe legalább 2 dolog kerül.

\(|A| = n, \quad |B| > n: \not\exists f: B \to A\) injektiv \(\land \not\exists f: A \to B\) szürjektív

\(|A| = |B| = n\quad f: A \to B\) (injektív \(\iff\) szürjektív)

Képletek

6 képlet: permutáció, variáció, kombináció

Permutáció

Egy \(n\) elemű \(A\) halmaz egy permutációja: az elemeiből képzett \(n\) hosszú sorozat, melyben mindegyik elem pontosan egyszer szerepel

Másképp: egy \(f:\{1,2,\dots,n\} \to A\) bijektív függvény

Pl.: \(A = \{x, y, z\}\)

\(x, y, z \longleftrightarrow 1 \to x, 2 \to y, 3 \to z\)

Más defininíció: \(f: A \to A\) bijektív függvény

Szükséges függvény: faktoriális

\(n \in \N: n! = \begin{cases}1, \text{ha }n = 0 \\ n \dot (n-1)!, \text{ha } n \geq 1 \end{cases}\)

Megjegyzés: \(n! = 1\cdot 2 \cdot 3 \cdot \ldots \cdot n\)

Stirling formula: \(n! \approx \sqrt{2 \pi n} \left(\frac ne\right)^n\)

Permutációk száma

Egy \(n\) elemű halmaznak \(n!\) db permutációja van

Bizonyítás: teljes indukcióval

n=0,1-re jó

Ha n-re ok \(\substack{? \\ \Rightarrow} (n+1)\)-re

Legyen \(|A| = n+1\), és képezzünk egy \(n+1\) hosszú sorozatot

  • Mi az utolsó eleme? \(\rightarrow\) \(n+1\) féle eset lehetséges
  • Mi az első \(n\) elem?
    • A maradék \(n\) elem permutációja az indukciós feltevés miatt: \(n!\) eset

\(\Rightarrow\) az esetek száma \((n+1)\cdot n! = (n+1)!\)

Másképp: A permutációkra vezessünk be egy relációt:

\(PERM_1 \sim PERM_2 \iff\) ha az utolsó elem ugyanaz.