1.Elementy zasady przeliczania z przykłądami: prawo mnożenia, dodawania i ogólne prawo mnożenia.
Prawo mnożenia (iloczynu):
a) Dla sończonych zbiorów S1,S2,…,Sk mamy
|S1xS2x…xSk| = j=1k|Sj|.
b) Ogólniej, załózmy, że mamy zbiór ciągów (s1,s2,…,sk) długości k o następującej strukturze. Jest n1 możliwości wyboru s1, dla ustalonych s1 i s2 sąn3 możliwości wyboru s3, i ogólnie, mając s1,s2,…,sj-1 możemy wybrać sj na nj sposobów. Wówczas nasz zbiór ma n1n2*…*nk elementów.
Prawo dodawania(sumy):
Niech S i T będązbiorami skończonymi.
a) Jeśli zbiory S i T sąrozłączne, tzn S∩T=∅, to |S∩T|=|S|∪|T|.
b) Ogólnie, |S ∪T|=|S| + |T| -|S∩T|.
2.Na czym polega zasada bijeknij? Przykłady.
Fukncja wzajemnie jednoznaczna (bijekcja)- funkcja będąca jednocześnie funkcją różnowartościową i „na”.Innymi słowy, bijekcja to funkcja (relacja przyporządkowująca każdemu elementowi dziedziny dokładnie jeden element obrezu) taka, że każdemu elementowi obrazu odpowiada dokładnie jeden element dziedziny.
Np. dla każdego x podporządkowany jest jakiś y.np( f(x)= 5.)
3.Schematy wyboru: warjacje z powtórzeniami, bez powtórzeń.
a) Warjacje z powtórzeniami- Warjacją k-elementową z powtórzeniami utworzoną ze zbioru n-elementowego nazywamy każdy k-wyrazowy ciąg różnych lub nie różniących się elementów z tego zbioru. Z k-wyrazowymi warjacjami z powtórzeniami zbioru n-elementowego mamy do czynienia wówczas, gdy k razy wybieramy po jednym elemencie ze zwracaniem z danego zbioru. Z trzech danych elementów: a, b, c , można utworzyć następujące dwuelementowe wariacje z powtórzeniami: {a,a},{a,b},{a,c},{b,a},{b,b},{b,c},{c,a},{c,b},{c,c}.
Liczba k-wyrazowa warjacji z powtórzeniami zbioru n-elementowego wyraża się wzorem:
Wnk=nk.
b) Wariacje bez powtórzeń- Warjacją k-elementową bez powtórzeń utworzoną ze zbioru n-elementowego (k≤n) nazywamy każdy k-wyrazowy ciąg różnych elementów z tego zbioru.
Wariacje spełniająnastępujące warunki:
-obejmują jedynie określoną liczbę k spośrób danych n elementów,
-istotna jest kolejność elementów wariacji.
Z k- wyrazowymi warjacjami bez powtórzeń zbioru złożonego z n elementów mamy do czynienia, gdy k razy wybieramy bez zwracania po jednym elemencie z danego zbioru. n-wyrazowe warjacje bez powtórzeń zbioru n-elementowego są permutacjami tego zbioru.
Z trzech danych elementów: a, b,c, można utworzyć następujące dwuelementowe warjacje bez powtórzeń: {a,b},{a,c},{b,a},{b,c},{c,a},{c,b}.
Liczba k-wyrazowa warjacji bez powtórzeń zbioru n-elementowego wyraża sięwzorem:
Vnk=n!n-k!
4.Schematy wyboru:kombinacje z powtórzeniami, bez powtórzeń.
a) Kombinacja z powtórzeniami:
-Kolejność nie jest ważna
-elementy mogą się powtarzać
( kn+k-1)=( n-1n+k-1)
b)Kombinacja bez powtórzeń:
-kolejność nie jest ważna
-elementy nie mogą się powtarzać
Cnk=(kn)=n!k!n-k!
5.Problem ulic na Manchattanie.
Znajdujemy się w lewym dolnym rogu A i chcemy przejść najkrótszą drogą do prawego górnego rogu B. Na ile sposobów możemy to zrobić?
Każda najkrótsza droga z A do B składa się z 9 odcinków , w tym 6 w prawo i 3 w górę. Wyobraźmy sobie, że idąc taką drogą „kodujemy” ją zapisując ) po każdym odcinku w prawo i 1 po każdym odcinku w górę. Na przykład, droga na powyższym rysunku otrzyma kod
001010001
Operacja kodowania dróg ustala bijekcję między drogami a ciągami binarnymi długości 9 z dokładnie 3 jedynkami i 6 zerami. Z kolei tych ostatnich jest tyle ile jest 3-elementowych
(39)=9*8*73*2*1=84.
TWIERDZENIE :Liczba najkrótszych dróg z A do B w prostokątnej kracie o wymiarach k na l wynosi ( kk+l).
6.Trójkąt Pascala.
NA bokach trójkąta znajdują się liczby 1, a pozostałe powstają jako suma dwóch bezpośrednio znajdujących się nad nią.Liczby stojące w n-tym wierszu to kolejne współczynniki dwumianu Newtona- rozwinięcia (a+b)n.
Rys.
7.Dwumian Newtona
Potęgę dwumianu (x+y)n można rozwinąć w sumę jednomianów postaci axkyl. W każdym z tych jednomianów współczynnik a jest dodatnią liczbą całkowitą, a wykładniki przy x oraz y sumują się do n. Współczynniki a przy jednomianach są symbolami Newtona i nazywane są współczynnikami dwumianowymi.
TWIERDZENE: Jeśli x,y są dowolnymi elementami dowolnego pierścienia przemiennego (np.liczby całkowite, wymierne, rzeczywiste, zespolone), to każdą naturalną potęgę dwumian x+y można rozłożyć na sumę postaci
(x+y)n=(0n)xn+(1n)xn-1y+(2n)xn-2y2+(3n)xn-3y3+…+(nn)yn
Gdzie (kn) oznacza odpowiedni współczynnik dwumianowy.
Przyjmując x0=y0=1 (także w przypadku, gdy x=0 lub y=0) można powyższy wzór zapisać za pomocą notacji sumacyjnej
x+yn=k=0nnkxk-kyk.
8.Ciągi binarne. Pojęcie (m,n)-ciągu, serii, ciągów zdominowanych.
a) Ciąg zdominowany to taki ciąg binarny w którym na pierwszych i pozycjach znajduję się co najmniej tyle zer ile jedynek.
Zad.Ile jest ciągów binarnych, które składają się z 5 zer i 8 jedynek?
( 813)=( 513)=( nm+n)=( mm+n)
Jeżeli n >= m to liczba ciągów zdominowanych składających się z m jedynek i n zer wynosi:
(m,n)=n+1-mn+1( nn+m)b)Seria- Ciąg powtarzających się liczb
Np.1110000111
9.Liczby Catalana
Liczby Catalana są szczególnym ciągiem liczbowym. Ma on zastosowanie w wielu różnych aspektach kombinatoryki. Określony jest wzorem:
Cn=1n+1( n2n)= 2n!n+1!n! dla n>=0
Z racji tego, że liczby Catalana spełniają poniższą zależność:
Cn=( n2n)- ( n+1 2n) dla n>=1
Widoczne jest, ze każda z liczb Catalana jest naturalną.
10.Równania rekurencyjne (przykłady-np.wieża w Hanoi).
ZALEŻNOŚĆ REKURENCYJNA
an=an-1+3 ->Wzór ogólny
an=1
a2=a1+3=1+3=4
a3=a2+3=4+3=7
an=3n-2-> Wzór ogólny
a3=3*3-2=7
a5=3*5-2=13
PROBLEM WIEZY W HANOI
an=2n-1+1->wzór rekurencyjny
a1...
RezidentRnR