Kombinatoryka
Oznaczenia i
potrzebne definicje
-
Silnia
,
symbol
czyta się ,,n silnia", umownie
przyjmuje się, że
.
Wypiszmy kilka wartości silni: 1!=1,
2!=2, 3!=6, 4!=24, 5!=120, ....
Często
symbol
"trzeba widzieć" w zadaniach jako:

-
Współczynniki dwumianu Newtona
Dla
określamy liczbę
(symbol
czytamy
,,n nad k").
Jest to liczba
wyrazowych podzbiorów, jakie można
utworzyć ze zbioru
-elementowego.
Z równości

wynika, że liczba wszystkich
podzbiorów - włączając w to zbiór
pusty i cały zbiór - jakie można
utworzyć ze zbioru
-elementowego
jest równa 2n.
-
Ciągi i
zbiory elementów
(a,b) - para uporządkowana
(ciąg) dwóch elementów, ważne jest
to jakie elementy ją tworzą, ale
także ich kolejność,
{a,b} - para
nieuporządkowana (zbiór)
dwóch elementów, kolejność nie jest
ważna, {a,b} = {b,a}.
Podobnie dla trójek:
(a,b,c) - uporządkowana trójka,
czyli ciąg z trzech elementów,
{a,b,c} - zbiór trójelementowy.
-
Liczbę elementów
zbioru A nazywamy mocą tego
zbioru i oznaczamy
lub |A|.
-
Jeżeli
to moc
zawsze, dla dowolnych A i B:
Schematy wyboru
Niech A będzie zbiorem skończonym
-elementowym

Zajmiemy się losowym wybieraniem
elementów spośród
elementów tego zbioru.
Przed przystąpieniem do losowania trzeba
ustalić:
1. czy istotna jest kolejność w jakiej
wybieramy elementy. Inaczej - czy z
wylosowanych elementów tworzymy ciąg czy
zbiór,
2. czy wybrany element jest zwracany do
zbioru A. Inaczej - czy losowanie jest
,,bez zwracania" czy ,,ze zwrotem".
Zasady przeliczania
Prawo
dodawania
Jeżeli zbiory A i B są
rozłączne, tzn. gdy
to

Tak samo dla większej
liczby rozłącznych zbiorów.
Przeliczanie zbiorów (liczby wyborów)
metodą prymitywną tzn. przez wypisanie
wszystkich możliwości, ma sens wówczas,
gdy liczba elementów zbioru jest mała. W
przeciwnym razie trzeba znać wzór na
liczbę wyborów lub metodę przeliczania.
Są cztery podstawowe schematy zliczania
- schematy kombinatoryczne.
1. Losujemy bez zwracania
elementów
i ustawiamy je kolejno - tworzymy
-wyrazowy
ciąg. Każdy z powstałych ciągów nazywa
się wariacją bez powtórzeń
z
elementów po
elementów.
2. Losujemy ze
zwrotem
elementów
i ustawiamy je kolejno - tworzymy
-wyrazowy
ciąg. Każdy z takich ciągów nazywa się
wariacją z powtórzeniami
z
elementów po
elementów.
3. Mamy zbiór
elementowy. Elementy tego zbioru
ustawiamy w ciąg
lub - co na jedno wychodzi - numerujemy
je od 1 do
Każdy z takich ciągów nazywa się
permutacją
elementów.
Liczba wszystkich
możliwych sposobów ustawienia
(permutacji) różnych
elementów jest równa
4. Mamy zbiór
elementowy. Wybieramy z niego
elementów
bez zwrotu i tworzymy z nich zbiór,
kolejność nie ma znaczenia. Każdy z
takich zbiorów nazywamy
kombinacją
-elementową
ze zbiorów
-elementowego.
Dołączamy
jeszcze:
1. Wzór na liczbę podziałów niepustego
zbioru. Niech A będzie zbiorem
-elementowym,
który dzielimy na
rozłącznych podzbiorów składających się
z
elementów
Liczba różnych takich podziałów wyraża
się wzorem:

Np. Liczba różnych rozdań 52 kart po 13
dla każdego z czterech grających w
brydża jest równa

2. Wzór na liczbę rozmieszczeń
nierozróżnialnych
kul w
komórkach - czyli kombinacji z
powtórzeniami:

Np. Na ile sposobów
pasażerów może wysiąść z windy na
piętrach?

|