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 ∈ X}x r y ⇒ y r x

• Przechodnia: ∀_{x, y, z ∈ X}x 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 (a_n) i (b_n) są ciągami liczb rzeczywistych. Mówimy, że a_n = O(b_n), gdy istnieje liczba c ∈ R i liczba n₀ ∈ N takie, że nierówność |a_n| < c|b_n| zachodzi dla każdego n > n₀.

Z definicji wynika, że jeśli b_n ≠ 0 dla każdego n i a_n = O(b_n) to $\left| \frac{a_{n}}{b_{n}} \right| < c$.

Załóżmy, że (a_n) i (b_n) są ciągami liczb rzeczywistych. Mówimy, że a_n = o(b_n), gdy $\operatorname{}\frac{a_{n}}{b_{n}} = 0$. Jeżeli a_n = o(b_n), to także jest a_n = O(b_n).

Własności notacji O:

Niech f, g, h, z będą funkcjami asymptotycznie dodatnimi. Wówczas:

1. Dla dowolnej c > 0 jeśli f(n) = O(g(n)) to c ⋅ f(n) = O(g(n)).

2. Jeśli f(n) = O(g(n)) ∧ g(n) = O(h(n)) to f(n) = O(h(n))

3. 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ą c₁, c₂ > 0 oraz n₀ ∈ N takie, że dla dowolnego n > n₀ mamy c₁g(n) ≤ f(n) ≤ c₂g(n). Własności notacji O przenoszą się na notację Θ.

Piszemy f(n) = Ω(g(n)), gdy istnieją c > 0, n₀ ∈ N takie że dla dowolnego n > n₀ 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(n^a − ε) to T(n) = Θ(n^a)

• Jeżeli f(n) = Θ(n^a) to T(n) = Θ(n^a⋅lgn)

• Jeżeli istnieje ε > 0 oraz f(n) = Ω(n^a + ε) 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⁻¹(b) ma więcej niż r elementów.

Definicja i własności funkcji tworzącej

Załóżmy, że a₁, a₂, a₃, … jest ciągiem liczbowym. Funkcję $F\left( z \right) = \sum_{n = 0}^{\infty}{a_{n}z^{n}}$ nazywamy funkcją tworzącą ciągu a_n, gdzie z ∈ (−R,R), gdzie R jest promieniem zbieżności.

Jeśli (a_n) i (b_n), 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 y_n jest ciągiem, czyli y₁, y₂, y₃, … . Różnicą ciągu nazywamy ciąg y₂ − y₁, y₃ − y₂, … i oznaczamy go Δ(y_n).

Operator E: E^p(x) = y(x+p), gdzie dodatkowo E⁰(x) = y(x) = I (operator identyczności).

Δ = E − I

E = Δ + I

Twierdzenie Montmorta o sumowaniu nieskończonym:

Niech Ea_n = a_n + 1 i Δa_n = a_n + 1 − a_n. 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 n^k.

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 A₁, …,  A_k takich że liczba elementów zbioru A_j = n i elementy zbioru A_j są dla nas nie rozróżnialne, to liczba permutacji jest równa $\frac{n!}{n_{1}! \cdot \ldots \cdot n_{k}!}$