KOMBINATORYKA

Tw: funkcji ze zb n-el. do zb k-el jest kⁿ

D: (indukcja) Dla 1-el dziedziny wzór k¹ jest jasny. Zał,że dla n-el dziedziny zachodzi kⁿ. Dla n+1 –el dziedziny wyróżniam jeden elem a. Dziedzina bez el. a ma n-el, a więc funkcji z tej okrojonej dziedziny jest kⁿ.

Tw: Ilość f-cji różnowart. Ze zb n-el w zb k-el wynosi k(k-1)…(k-n+1)

D:Ustawmy el dziedz w ciąg. Na 1 miejscu może być k-el. Na drugim k-1. Na n-tym może być k-n+1. Wszystkich jest k(k-1)…(k-n+1)

Df: Permutacją zb nazywamy f-kcje „1-1” i „na” z tego zb w siebie.

Wn: Ilość permutacji zb n-el wynosi n(n-1)…(n-n+1)=n!

Tw: Ilość podzbiorów k-el zb n-el oznaczamy ( ⁿ_k) i wynosi ona n!/k!(n-k)!

Tw: (Dwumian Newtoona) Dla liczby naturalnej n oraz R₊ zachodzi (1+t)ⁿ= ∑ _i=0 (ⁿ_i) tⁱ

Df: Dla zb A przez |A| oznaczamy ilość el A

Tw: (Zasada szufladkowa Dirichleta) Jeśli zb A podzielić na k rozłącznych podob. to któryś podob. ma co najmniej |A| /k elementów (/ to kreska ulamkowa)

Tw: (Zasada włączania i wyłączania) Niech A_i zawarte w X : i ϵ {1,..,n}. Liczba el X które nie należa do żadnego A_i wynosi: ∑ _Ie{1,..,n} (-1)^|I| |A_I| (I-podzb zb {1,..,n} , A_I –przekrój zb A_i t,że ieI)

Przykład: Ile jest liczb 7 cyfrowych mających 1 i 2 i 3?

Wszystkich jest: |A₁|= 9∙10⁶ ; liczb bez 2 |A₂|=|A₃|=8∙9⁶ ; liczb bez 1 i 2 |A_1,2|=|A_1,3|=|A_2,3|=7∙8⁶ ; liczby bez 1,2,3 |A_1,2,3|=6∙7⁶ ; Ilość dobrych liczb: 9∙10⁶ -3|A₂|+3|A_1,2|-|A_1,2,3|

Zad: Na płaszczyźnie R² mamy siatkę dróg (lini) o całkowitej jednej współrz. Ilejest najkrótszych dróg z (0,0) do (m,k)? Każda dobra droga ma m odc poziomych i k odc pionowych. W sumie jest k+m odc.

Dróg jest tyle ile wyborów k odcinków, a tych jest (^m+k _k) = (^m+k _m)

Rysunek:

TEORIA LICZB

Tw: (o dzieleniu z resztą) Dla dowolnych liczb a,b ϵ N, b różne 0 istnieją jedyne liczby x i r t,że a=xb+r oraz 0≤ r<b

Df: Mówimy, że liczba a przystaje do b modulo m, gdy m|a-b. Piszemy a≡b (mod m)

Fakcik: Relacja przystawania jest rel równoważn, czyli: 1.a≡a (mod m) 2.a≡b (mod m) b≡a (mod m) 3.a≡b (mod m) i b≡c (mod m) a≡c (mod m)

Tw: Jeśli a≡b (mod m) i c≡d (mod m), to: 1. a+-c ≡ b+-d (mod m) 2. ac≡bd (mod m)

D: m|a-b , m|c-d => m|a-b +- (c-d). Ponieważ ac-bd =a(c-d) + d(a-b), to jeśli m|a-b i m|c-d to m|a(c-d)+d(a-b)

Df: Pierścień Z_/m ={0,1,…,m-1} z działaniami +_m i *_m , plus mod m i razy mod m. Np. 5*₁₁7=2 w Z_/

Df: Największy wspólny dzielnik a i b to największa liczba dzieląca jednocześnie a i b. oznacz NWD_(a,b)

Tw: Dla dowolnych a,b istnieją liczby x,y t,że xa+yb=NWD_(a,b)

Tw: Algorytm Euklidesa

NWD= a dla b=0 i NWD(b,a mod b) dla b ≥1

Df: Liczby a i b są względnie pierwsze gdy nie mają wspólnych dzielników czyli ich NWD jest jeden.

Wn: Liczby a,b są wzgl pierwse gdy istnieją x,y t,że xa+yb=1

Df: Liczba jest pierwsza, gdy dzieli się przez 1 (-1) i przez samą siebie. (przyjmujemy, że 1 nie jest pierwsza)

Tw: Każda liczba naturalna n zapisuje się jednoznacznie z dokładnością do kolejności w postaci n=p₁^k1_*p₂^k2_*..._*p_n^kn , gdzie p_i - różne l pierwsze, k_i - l naturalne

Tw: (chińskie o resztach) Niech liczby m₁,,…,m_n są parami względnie pierwsze oraz liczby a₁,…,a_n są dowolne. Istnieje liczba x t,że x≡a_i (mod m_i) *(co więcej liczba ta jest jedyna modulo m_1*m_2*…_*m_n=

D: (cz.* Co więcej) Weźmy dwie liczby x i x’ spełniające x≡a_i (mod m_i) oraz x’≡a_i (mod m_i). Zatem x-x’ dzieli się przez m_i

(cz.2) Możemy zał, że a_i e {0,…,m_i-1} (czyli, ze a_i jest reszta z dzielenia przez m_i). jeśli r_i jest reszta z dzielenia a_i przez m_i to warunek x≡a_i(mod m_i) jest równoważny warunkowi x≡r_i(mod m_i) (bo a_i=r_i)

Zasada indukcji Jeżeli zb P zawarty w N oraz 0ϵP, V_neN nϵP => n+1ϵP to P=N

Zasada minimum: Każdy niepusty zbiór N ma w sobie el najmniejszy.

Zasada maksimum: Każdy niepusty i ograniczony zb N ma w sobie el największy.

Tw: N ma wszystkie te zasady.

Tw: Trzy powyższe zasady są równoważne w N.

GRAFY

Df: Graf to para zbiorów (V,E) gdzie V-zb wierzchołków a E- zb pewnych dwuelem podzbiorów V.

Np.

Df: Niech veV. d(v) to ilość krawędzi wychodzących z V czyli ilość podzbiorów dwuelem w których jest V. Liczba d(v) nazywa się stopniem wierzchołka.

Tw: W dowolnym grafie G=(V,E) ∑ _veV d(v)=2|E|

Df: Dwa grafy G=(V_G,E_G) , H=(V_H,E_H) są izomorficzne, gdy istnieje izomorfizm, czyli f-cje f:V_G->V_H (bijekcja).

Np. są izomorficzne (wystarczy je inaczej narysować.)

Tw: Jeśli G=(V_G,E_G) , H=(V_H,E_H) są izomorficzne to:

(i)mają tyle samo wierzchołków |V_G|=|V_H|

(ii)mają tyle samo krawędzi |E_G|=|E_H|

(iii)mają tyle samo wierzchołków stopnia k dla każdego k. (tw się nie odwraca!)

Przykład:

Te grafy maja po tyle samo wierzchołków, krawędzi i wierzchołków danego stopnia a nie są izomorficzne.

Df: Drogą lub ścieżką w grafie G nazywamy ciąg wierzchołków v₀,..,v_n t,że {v,v_n+1}e E_G jest krawędzią

Df: Droga prostą jest droga bez powtarzających się wierzchołków.

Df: Cyklem jest droga v₀,…,v_n t,że v₀,..,v_n-1 jest prosta oraz v₀=v_n

Tw: Jeśli wierzchołki v i u są połączone drogą to są też połączone drogą prostą.

Tw: Jeżeli wierzchołki u i v (u różne v) można połączyć dwiema różnymi drogami prostymi to istnieje cykl.

Rysunek:

Tw: Jeżeli każde dwa wierzchołki można połączyć co najwyżej jedną droga prostą to graf jest a-cykliczny.

Df: Graf jest spójny jeśli każde dwa wierzchołki można połączyć drogą.

Np.

Df: Drzewem nazywamy graf spójny i a-cykliczny

Np.

Tw: Warunki są równoważne: (i) G jest drzewem ; (ii) G jest spójny ale usunięcie dowolnej krawędzi psuje spójność ; (iii) G jest acykliczny ale dodanie jakiejś krawędzi psuje a-cykliczność.

Tw: W drzewie o n wierzchołkach mamy n-1 krawędzi.

Tw: Niech G to graf z wierzchołkami, wtedy n.w.s.r: (i) G jest drzewem; (ii) G ma n+1 krawędzi i jest spójny; (iii) G ma n+1 krawędzi i jest a-cykliczny.

Df: Droga Eulera to droga przechodząca przez wszystkie krawędzie.

Cykl Eulera to droga zamknięta V₀=V_ostatnie

Tw: Spójny graf ma cykl Eulera <= > ma wszystkie wierzchołki parzystego stopnia.

D: Niech G ma cykl Eulera. Wędrując tym cyklem usuwamy krawędzie przez które już przeszliśmy. Przechodząc przez jakiś wierzchołek ‘wewnątrz drogi’ usuwamy dwie krawędzie wychodzące z niego.

Tw: Ścieżka Hamiltona – ścieżka w grafie przebiegająca przez wszystkie jego wierzchołki dokładnie raz

Tw: Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu przechodzony jest tylko jeden raz (oprócz pierwszego wierzchołka)

Tw: Graf hamiltonowski to graf rozważany w teorii grafów zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek dokładnie jeden raz zwaną ścieżką Hamiltona. W szczególności grafem hamiltonowskim jest graf zawierający cykl Hamiltona, tj. zamkniętą ścieżkę Hamiltona

Liczba jest podzielna przez 3, gdy suma jej cyfr jest liczbą podzielną przez 3.
Liczba jest podzielna przez 9, gdy suma jej cyfr jest liczba podzielną przez 9.

Liczba jest podzielna przez 11 jeżeli różnica pomiędzy sumą cyfr stojących na miejscach
nieparzystych (licząc od prawej) i sumą cyfr stojących na miejscach parzystych jest liczbą
podzielną przez 11.
Przykład: 175978 bo (8+9+7) - (7+5+1) = 24-13 = 11

Które grafy są izomorficzne?

Odp. 1,2,7 i 5,6