Zasada indukcji
(M⊂ℕ∧1∈M∧∀x(x∈M)⇒(x+1)∈M) ⇒ M=ℕ
Zasada minimum
Każdy podzbiór zbioru ℕ ma element najmniejszy.
Zasada maksimum
Każdy ograniczony z góry podzbiór zbioru ℕ ma element największy.
Zasada Archimedesa
Dla dowolnej liczby rzeczywistej x∈ℝ, dowolnej liczby rzeczywistej x∈ℝ takiej że 0 > y istnieje liczba naturalna k∈ℕ, taka że x < ky. W szczególności jeśli y = 1, to mamy, że dla każdej liczby rzeczywistej x istnieje taka liczba naturalna k, taka że x < k.
Relacja w zbiorze X
Nazywamy nią dowolny podzbiór iloczynu kartezjańskiego X × X
Relacja równoważności
Mówimy że relacja r jest relacją równoważności, gdy jest ona jednocześnie:
Zwrotna: ∀x ∈ Xx r x
Symetryczna: ∀x, y ∈ Xx r y ⇒ y r x
Przechodnia: ∀x, y, z ∈ Xx r y ∧ y r z ⇒ x r z
Działania na pierścieniach ℤp
Dla dowolnego p∈ℕ i dla a, b ∈ ℤp definiujemy
$a\bigoplus_{p}^{}b =$ reszta z dzielenia a + b przez p
$a\bigodot_{p}^{}b =$ reszta z dzielenie a ⋅ b przez p
Równanie modulo p
Funkcja sufitu i sufitu
Dla dowolnej liczby rzeczywistej x zbiór {n∈Z, n≤x} jest ograniczeniem z góry, zatem zgodnie z zasadą maksimum ma element największy, który nazywamy częścią całkowitą i oznaczamy symbolem ⌊x⌋. Zwana jest też funkcją podłogi.
⌊x⌋ ≤ x < ⌊x⌋ + 1
Dla dowolnej liczby rzeczywistej x zbiór {m∈Z, x≤m} jest ograniczeniem z dołu, zatem zgodnie z zasadą minimum ma element najmniejszy. Oznaczamy go symbolem ⌈x⌉
⌈x⌉ − 1 < x ≤ ⌈x⌉
Własności:
x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1
⌊x⌋ = n ⇔ n ≤ x < x + 1
⌈x⌉ = m ⇔ m − 1 < x ≤ m
Dla liczby całkowitej n: $\left\lceil \frac{n}{2} \right\rceil + \left\lfloor \frac{n}{2} \right\rfloor = n$
Dla n, a, b ∈ Z mamy: $\left\lceil \frac{\left\lceil \frac{n}{a} \right\rceil}{b} \right\rceil = \left\lceil \frac{n}{(a,b)} \right\rceil$, analogicznie dla podłogi.
Notacje
Załóżmy, że (an) i (bn) są ciągami liczb rzeczywistych. Mówimy, że an = O(bn), gdy istnieje liczba c ∈ R i liczba n0 ∈ N takie, że nierówność |an| < c|bn| zachodzi dla każdego n > n0.
Z definicji wynika, że jeśli bn ≠ 0 dla każdego n i an = O(bn) to $\left| \frac{a_{n}}{b_{n}} \right| < c$.
Załóżmy, że (an) i (bn) są ciągami liczb rzeczywistych. Mówimy, że an = o(bn), gdy $\operatorname{}\frac{a_{n}}{b_{n}} = 0$. Jeżeli an = o(bn), to także jest an = O(bn).
Własności notacji O:
Niech f, g, h, z będą funkcjami asymptotycznie dodatnimi. Wówczas:
Dla dowolnej c > 0 jeśli f(n) = O(g(n)) to c ⋅ f(n) = O(g(n)).
Jeśli f(n) = O(g(n)) ∧ g(n) = O(h(n)) to f(n) = O(h(n))
Jeśli f(n) = O(g(n)) ∧ h(n) = O(z(n)) to f(n) ⋅ h(n) = O(g(n)⋅z(n)) oraz f(n) + h(n) = O(g(n)+z(n)), a także f(n) + h(n) = O(max{g(n),z(n)})
Piszemy f(n) = Θ(g(n)) gdy istnieją c1, c2 > 0 oraz n0 ∈ N takie, że dla dowolnego n > n0 mamy c1g(n) ≤ f(n) ≤ c2g(n). Własności notacji O przenoszą się na notację Θ.
Piszemy f(n) = Ω(g(n)), gdy istnieją c > 0, n0 ∈ N takie że dla dowolnego n > n0 mamy f(n) ≥ c ⋅ g(n).
Twierdzenie o rekurencji uniwersalnej
Zakładamy, że a ≥ 1, b > 1 są stałymi, a f(n) jest funkcją zmiennej n ∈ N. Załóżmy, że funkcja T(n) jest zdefiniowana dla n przez następującą rekurencję: $T\left( n \right) = aT\left( \frac{n}{b} \right) + f\left( n \right)$, gdzie $\frac{n}{b}$ dane jest przez $\left\lfloor \frac{n}{b} \right\rfloor$ lub $\left\lceil \frac{n}{b} \right\rceil$, wtedy:
Jeżeli istnieje ε > 0 oraz f(n) = O(na − ε) to T(n) = Θ(na)
Jeżeli f(n) = Θ(na) to T(n) = Θ(na⋅lgn)
Jeżeli istnieje ε > 0 oraz f(n) = Ω(na + ε) oraz istnieje c ∈ (0, 1) takie, że $\text{af}\left( \frac{n}{b} \right) \leq c \cdot f\left( n \right)$, to T(n) = Θ(f(n))
Zasada szufladkowa Dirichleta
Nie można umieścić 5 królików w 4 klatkach, tak aby w każdej był co najwyżej jeden królik.
Jeżeli X jest zbiorem x elementowym, a Y jest zbiorem y elementowym i x > y to nie istnieje funkcja różnowartościowa f : X → Y.
Ogólna zasada Dirichleta:
Dla dowolnych liczb naturalnych s, r, t takich, że s > r ⋅ t i dowolnej funkcji f : S → T, gdzie liczba elementów S jest równa s, a liczba elementów T jest równa t, istnieje takie b ∈ T, że zbiór f−1(b) ma więcej niż r elementów.
Definicja i własności funkcji tworzącej
Załóżmy, że a1, a2, a3, … jest ciągiem liczbowym. Funkcję $F\left( z \right) = \sum_{n = 0}^{\infty}{a_{n}z^{n}}$ nazywamy funkcją tworzącą ciągu an, gdzie z ∈ (−R,R), gdzie R jest promieniem zbieżności.
Jeśli (an) i (bn), n = 0, 1, 2, … są dwoma ciągami liczb a funkcje A$\left( z \right) = \sum_{n = 0}^{\infty}{a_{n}z^{n}}$ i $B\left( z \right) = \sum_{n = 0}^{\infty}{b_{n}z^{n}}$ odpowiednio ich funkcjami tworzącymi to następujące operacje na ciągach generują następujące funkcje tworzące:
Sumowanie: A(z) + B(z) jest funkcją tworzącą dla ciągu $\sum_{n = 0}^{\infty}{\left( a_{n} + b_{n} \right)z^{n}}$
Przesunięcie w prawo: $\text{zA}\left( z \right) = \sum_{n = 0}^{\infty}{a_{n - 1}z^{n}}$
Przesunięcie w lewo: $\frac{A\left( z \right) - a_{0}}{z} = \sum_{n = 0}^{\infty}{a_{n + 1}z^{n}}$
Mnożenie przez indeks (różniczkowanie): $A^{'}\left( z \right) = \sum_{n = 0}^{\infty}{(n + 1)a_{n + 1}z^{n}}$
Dzielenie przez indeks (całkowanie): $\int_{0}^{x}{A\left( t \right)\text{dt}} = \sum_{n = 0}^{\infty}{\frac{a_{n - 1}}{n}\ z^{n}}$
Operatory Δ i E
Załóżmy że yn jest ciągiem, czyli y1, y2, y3, … . Różnicą ciągu nazywamy ciąg y2 − y1, y3 − y2, … i oznaczamy go Δ(yn).
Operator E: Ep(x) = y(x+p), gdzie dodatkowo E0(x) = y(x) = I (operator identyczności).
Δ = E − I
E = Δ + I
Twierdzenie Montmorta o sumowaniu nieskończonym:
Niech Ean = an + 1 i Δan = an + 1 − an. Wówczas $a_{0} + a_{1}x + a_{2}x^{2} + \ldots + a_{r}x^{r} + \ldots = \frac{a_{0}}{1 - x} + \frac{x\Delta a_{0}}{\left( 1 - x \right)^{2}} + \frac{x\Delta^{2}a_{0}}{\left( 1 - x \right)^{3}} + \ldots$
Podać wzór na liczbę elementów zbioru A + B+ … znając liczbę ich przesunięć (podany wzór)
Kombinatoryka
Wariacją bez powtórzeń k wyrazową zbioru n elementowego nazywamy każdy k wyrazowy ciąg różnych elementów tego zbioru i wyliczmy ją ze wzoru $\frac{n!}{\left( n - k \right)!}$.
Wariacją z powtórzeniami k wyrazową zbioru n elementowego nazywamy każdy k wyrazowy ciąg elementów tego zbioru i wyliczmy ją ze wzoru nk.
Permutacją zbioru n elementowego nazywamy każdą n wyrazową wariację bez powtórzeń tego zbioru. Wyliczamy ze wzoru n!
Kombinacją k elementową zbioru A n elementowego nazywamy dowolny k elementowy podzbiór zbioru A. Liczba wszystkich kombinacji jest równa $\begin{pmatrix} n \\ k \\ \end{pmatrix}$.
Kombinacje z powtórzeniami: n przedmiotów można umieścić na k miejscach na $\begin{pmatrix} n + k - 1 \\ k - 1 \\ \end{pmatrix} = \frac{\left( n + k - 1 \right)!}{\left( k - 1 \right)!n!}$ sposobów.
Permutacje z powtórzeniami: Liczba permutacji zbioru n elementowego o podzbiorach A1, …, Ak takich że liczba elementów zbioru Aj = n i elementy zbioru Aj są dla nas nie rozróżnialne, to liczba permutacji jest równa $\frac{n!}{n_{1}! \cdot \ldots \cdot n_{k}!}$