...Wariacja z powtórzeniami. k-elementowa wariacja z powtórzeniami ze zbioru n-elementowego nazywamy liczbe mozliwych wyborów k elementów z n-elementowego zbioru, przy czym wybierane elementy moga sie powtarzac, a ich kolejnosc ma znaczenie....
....Kombinacja z powtórzeniami. k-elementowa kombinacja z powtórzeniami ze zbioru n-elementowego nazywamy liczbe mozliwych wyborów k elementów z nelementowego zbioru, przy czym kolejnosc wybieranych elementów nie ma znaczenia, a elementy moga sie powtarzac (wybrane elementy tworza multizbiór).....
MATEMATYKA DYSKRETNA 2011/12ZESTAW 01
PODSTAWY KOMBINATORYKI
1. TEORIA
Dany niech będzie n-elementowy zbiór X, n > 0, oraz liczba naturalna k taka,
że 0 < kn. Klasycznym problemem kombinatorycznym jest pytanie o to, na
ile sposobów można ze zbioru X wybrać k elementów. Należy jednak ustalić dwierzeczy: po pierwsze, czy wybrane elementy mogą się powtarzać; po drugie, czykolejność wyboru elementów jest istotna. Jak widać, istnieją cztery różne schematywyboru.Wariacja z powtórzeniami. k-elementową wariacją z powtórzeniami ze zbiorun-elementowego nazywamy liczbę możliwych wyborów k elementów z n-elemento-wego zbioru, przy czym wybierane elementy mogą się powtarzać, a ich kolejnośćma znaczenie.Wariacja bez powtórzeń. k-elementową wariacją bez powtórzeń ze zbioru n-e-lementowego nazywamy liczbę możliwych wyborów k elementów z n-elementowegozbioru, przy czym wybierane elementy nie mogą się powtarzać, a ich kolejność maznaczenie.Kombinacja bez powtórzeń. k-elementową kombinacją bez powtórzeń (lub pro-ściej: kombinacją) ze zbioru n-elementowego nazywamy liczbę możliwych wyborówk różnych elementów z n-elementowego zbioru, przy czym kolejność wybieranychelementów nie ma znaczenia.Kombinacja z powtórzeniami. k-elementową kombinacją z powtórzeniami zezbioru n-elementowego nazywamy liczbę możliwych wyborów k elementów z n-elementowego zbioru, przy czym kolejność wybieranych elementów nie ma znacze-nia, a elementy mogą się powtarzać (wybrane elementy tworzą multizbiór).
Szczególnym przypadkiem wariacji bez powtórzeń, dla k = n, jest permutacja.Permutacja. Permutacją zbioru n-elementowego nazywamy liczbę możliwych uło-żeń elementów tego zbioru w ciąg.Oznaczenia. Wprowadźmy oznaczenia dla powyższych schematów. Dla ustalo-nych k oraz n będziemy pisać:• W k - na oznaczenie wariacji z powtórzeniamin• V k - na oznaczenie wariacji bez powtórzeńn• Ck - na oznaczenie kombinacji z powtórzeniamin• Ck - na oznaczenie kombinacji bez powtórzeńn• n! - na oznaczenie permutacji
12
PODSTAWY KOMBINATORYKI
Symbol ”!” nazywany jest silnią, a symbol n – symbolem Newtona. Definicjęk
symbolu Newtona można rozszerzyć, pozwalając, by liczba n wn
była liczbąk
rzeczywistą (lub nawet zespoloną), definiując:nn(n−1)...(n−k+1)
dla k
0,
(1)
=k(k−1)...2·1k
0
dla k < 0.
Zauważmy, że w przypadku uogólnionego symbolu Newtona n = 1 tylko dlann
0. Dla n < 0 mamy n = 0.nMetoda ustalania bijekcji. Jeśli mamy zliczyć ilość elementów jakiegoś zbioruX, ale policzenie ich wprost nie jest łatwe i nie da się bezpośrednio zastosować pod-stawowych wzorów kombinatorycznych, można wtedy użyć tzw. metody ustalania
(…)
…, że taka bijekcja istnieje, oznacza to, że liczność
zbioru X jest równa liczności zbioru Y .
ZADANIA
Zadanie 1. Ile jest wszystkich funkcji f : X → Y , gdzie |X| = k > 0, |Y | = n > 0?
Zadanie 2. Ile jest wszystkich funkcji różnowartościowych f : X → Y , gdzie
|X| = k > 0, |Y | = n > 0?
Zadanie 3. Ile jest przekątnych w n-kącie foremnym?
Zadanie 4. Na ile sposobów można wybrać k > 0 elementów z n-elementowego…
…. Ile jest ciągów binarnych o długości n > 0?
Zadanie 8. Ile jest wszystkich podzbiorów zbioru n-elementowego, n > 0?
Zadanie 9. Na ile sposobów można zapisać w jednym rzędzie cyfry 0, 1, ..., 9 tak,
by 8 i 9 stały obok siebie?
Zadanie 10. Na ile sposobów można posadzić przy okrągłym stole n > 0 osób?
Zadanie 11. Ile jest kostek domina w zestawie, w którym oczka na połówkach
kostek domina mogą przyjmować wartości…
... zobacz całą notatkę
Komentarze użytkowników (0)