ZESTAW 01
PODSTAWY KOMBINATORYKI
1. TEORIA
Dany niech będzie n-elementowy zbiór X, n > 0, oraz liczba naturalna k taka, że 0 < k ¬ n. Klasycznym problemem kombinatorycznym jest pytanie o to, na
ile sposobów można ze zbioru X wybrać k elementów. Należy jednak ustalić dwie rzeczy: po pierwsze, czy wybrane elementy mogą się powtarzać; po drugie, czy
kolejność wyboru elementów jest istotna. Jak widać, istnieją cztery różne schematy
wyboru.
Wariacja z powtórzeniami. k-elementową wariacją z powtórzeniami ze zbioru
n-elementowego nazywamy liczbę możliwych wyborów k elementów z n-elementowego 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-elementowego nazywamy liczbę możliwych wyborów k elementów z n-elementowego
zbioru, przy czym wybierane elementy nie mogą się powtarzać, a ich kolejność ma
znaczenie.
Kombinacja bez powtórzeń. k-elementową kombinacją bez powtórzeń (lub pro-
ściej: kombinacją) ze zbioru n-elementowego nazywamy liczbę możliwych wyborów
k różnych elementów z n-elementowego zbioru, przy czym kolejność wybieranych elementów nie ma znaczenia.
Kombinacja z powtórzeniami. k-elementową kombinacją z powtórzeniami ze
zbioru 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órzeniami
n
• V k - na oznaczenie wariacji bez powtórzeń
n
• e
Ck - na oznaczenie kombinacji z powtórzeniami
n
• Ck - na oznaczenie kombinacji bez powtórzeń
n
• n! - na oznaczenie permutacji
1
PODSTAWY KOMBINATORYKI
Symbol ”!” nazywany jest silnią, a symbol n – symbolem Newtona. Definicję k
symbolu Newtona można rozszerzyć, pozwalając, by liczba n w
n była liczbą
k
rzeczywistą (lub nawet zespoloną), definiując:
(
n
n( n− 1) ... ( n−k+1)
dla k 0 ,
(1)
=
k( k− 1) ... 2 · 1
k
0
dla k < 0.
Zauważmy, że w przypadku uogólnionego symbolu Newtona n = 1 tylko dla
n
n 0. Dla n < 0 mamy n = 0.
n
Metoda ustalania bijekcji. Jeśli mamy zliczyć ilość elementów jakiegoś zbioru
X, 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
bijekcji. Polega ona na ustaleniu bijektywnego odwzorowania pomiędzy elementami,
które mamy policzyć, a elementami zbioru Y , którego elementy da się już zliczyć w
łatwy sposób. Jeśli uda się pokazać, ż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 zbioru, n > 0, jeśli kolejność wybranych elementów nie ma znaczenia i wybrane
elementy mogą się powtarzać?
Zadanie 5. Ile jest funkcji niemalejących ze zbioru k-elementowego w zbiór n-
elementowy, k, n > 0?
Zadanie 6. Na ile sposobów można rozmieścić k > 0 rozróżnialnych kul w n > 0
rozróżnialnych pudełkach, jeśli pudełka zawierają uporządkowane ciągi elementów
(dopuszczamy ciągi puste)?
Zadanie 7. 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 0, 1, 2, 3, 4, 5, 6?
Zadanie 12. Ile jest różnych rozdań w brydżu?
Zadanie 13. Jakie jest prawdopodobieństwo, że w 30-osobowej grupie ćwiczenio-
wej istnieją dwie osoby obchodzące urodziny w tym samym dniu?