1. Zasada indukcji matematycznej
Niech dla każdego n ϵ N, p(n) będzie zdaniem które może być prawdziwe lub fałszywe. Aby udowodnić, że dla każdego n ≥ n0 zdanie p(n) jest prawdziwe, wystarczy pokazać, że
ñ p(n0) jest prawdziwe //warunek początkowy
ñ dla każdego k ≥ n0 ,
p(k) => p(k+1) //krok indukcyjny
(tzn. zdanie p(k+1) jest prawdziwe gdy p(k) jest prawdziwe)
Np.
1 ∙ 2 ∙ 3 ∙ ... ∙ n > 2n
2. Zasada szufladkowa
Jeśli rozmieścimy n przedmiotów w m szufladkach, przy czym n > k * m, to w którejś szufladce znajdzie się co najmniej k + 1 przedmiotów.
3. Podstawowe zasady i prawa przeliczania: zasada bijekcji, prawa dodawania i mnożenia
//Przeliczanie – wyznaczenie liczby elementów danego zbioru (w przypadku zbioru skończonego)
Zasada bijekcji
Pozwala zastąpić przeliczany zbiór innym, zawierającym tyle samo elementów. Zasada ta opiera się na obserwacji, że jeśli istnieje bijekcja dla skończonych zbiorów A oraz B,
f: A → B
to zbiory A i B mają taką samą liczbę elementów.
Bijekcja pomiędzy zbiorem wszystkich rozmieszczeń k jednakowych kul w n oznaczonych szufladkach, a zbiorem ciągów binarnych z k zer i n-1 jedynek
Przykładowe rozmieszczenie dla 6 kul i 4 szufladek, | to ścianka szufladki, o to kula:
|oo | |o |ooo|
W pierwszej szufladce są 2 kule, w drugiej 0, w trzeciej 1, w czwartej 3.
Można to rozmieszczenie zapisać ciągiem binarnym, gdzie 1 to ścianka, 0 to kula. Pierwszej i ostatniej ścianki nie zapisujemy ponieważ będzie ona występowała w każdym rozmieszczeniu.
001101000
Zasada mnożenia
Niech A1 , A2 …, An będą zbiorami skończonymi.
Wówczas liczba ciągów (a1, a2 …, an), gdzie ai ϵ Ai, i = 1, 2, …, n
wynosi |A1| ∙ |A2| ∙ ... ∙ |An|
|A| - liczba elementów zbioru A
Ewentualnie
|A1 × A2 × … × An| = |A1| ∙ |A2| ∙ ... ∙ |An|
× oznacza iloczyn kartezjański.
Jak mamy np. zbiory A = {1, 2, 3} oraz B = {5, 8} to zapis A × B będzie oznaczał zbiór par uporządkowanych:
{ {1, 5}, {1, 8}, {2, 5}, {2, 8}, {3, 5}, {3, 8} }.
Elementów tego zbioru jest |A| ∙ |B| = 3 * 2 = 6
Ile jest dwucyfrowych liczb zbudowanych z cyfr {1,2,3}
A1 = {1,2, 3} //pierwsza cyfra
A2 = {1,2, 3} //druga cyfra
|A1| = 3
|A2| = 3
A1 ∙ A2 = 3 ∙ 3 = 32 = 9
Wszystkie możliwości: 11, 12, 13, 21, 22, 23, 31, 32, 33
Prawo dodawania
Jeśli A1, A2, ... An są zbiorami skończonymi parami rozłącznymi (Ai ∩ Aj = ∅ dla i ≠ j, tzn. każde dwa zbiory spośród nich to zbiory rozłączne, czyli niemające części wspólnej. Czyli każdy element danego zbioru nie występuje w żadnym innym zbiorze), to
| suma zbiorów A1, A2, ... An | = Suma |A1|, |A2|, ... |An|
czyli
Liczba elementów sumy zbiorów A1, A2, ... An = Suma liczb elementów zbiorów A1, A2, ... An
Ile trzycyfrowych liczb zbudowanych z cyfr od 1 do 9 zawiera cyfrę 5?
B = {1, 2, … 9}
C = A \ {5}
1. Liczby postaci 5XY
X, Y ϵ B
|A1| = 9 ∙ 9
2. Liczby postaci X5Y
X ϵ C
Y ϵ B
|A2| = 8 ∙ 9
3. Liczby postaci XY5
|A3| = 8 ∙ 8
|A| = |A1| + |A2| + |A3|
Co jeśli zbiory nie będą rozłączne? Wtedy wchodzi zasada włączania i wyłączania.
4. Zasada włączania i wyłączania
Reguła kombinatoryczna, pozwalająca na określenie liczby elementów skończonej sumy mnogościowej skończonych zbiorów.
// Podobno nie trzeba czytać tego wzoru, tylko napisać
Wzór dla 3 skończonych zbiorów (A1 to A, A2 to B itd., obrazek z wiki )
|A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3| - | A1 ∩ A2| - |A1 ∩ A3| - | A2 ∩ A3| + | A1 ∩ A2...
RezidentRnR