Podstawowe pojęcia
Zadaniem kombinatoryki jest wyznaczanie liczby elementów zbiorów skończonych utworzonych zgodnie z określonymi zasadami. W tym celu konstruowane są spełniające pewne warunki odwzorowania jednego zbioru skończonego w drugi oraz znajdowane wzory na liczbę tych przekształceń. Podstawowe pojęcia, którymi posługuje się kombinatoryka, to zbiór oraz ciąg. Musimy więc przypomnieć sobie istotne w kombinatoryce różnice między zbiorem a ciągiem. Elementy w zbiorze nie mogą się powtarzać i ich kolejność nie jest ważna, natomiast wyrazy ciągu mogą się powtarzać i ważna jest ich kolejność. Zatem zamieniając kolejność elementów w zbiorze, otrzymujemy nadal ten sam zbiór, zaś zamieniając miejscami wyrazy w ciągu, dostajemy nowy ciąg.
Elementarną metodą kombinatoryki, często stosowaną intuicyjnie, jest tzw. reguła mnożenia i dodawania.
Elementarną metodą kombinatoryki, często stosowaną intuicyjnie, jest tzw. reguła mnożenia i dodawania.
Jeżeli dane są dwa zbiory skończone \(A\) i \(B\), z których zbiór \(A\) ma \(m\) elementów, a zbiór \(B\) ma \(n\) elementów, to liczba różnych par \((a,b)\), takich że \(a\in A\) i \(b\in B\), jest równa iloczynowi mocy tych zbiorów: \(m\cdot n\).
Zauważmy, że reguła mnożenia odpowiada iloczynowi kartezjańskiemu \(A\times B\) zbiorów skończonych \(A\) i \(B\), którego moc jest równa \(\overline{\overline {A\times B}}= \stackrel {=}{A}\cdot\stackrel {=}{B}\).
Jeżeli dane są dwa zbiory rozłączne \(A\) i \(B\), z których zbiór \(A\) ma \(m\) elementów, a zbiór \(B\) ma \(n\) elementów, to moc zbioru \(A\cup B\) jest równa sumie mocy tych zbiorów: \(m+n\).
Widzimy, że reguła dodawania oparta jest na sumie \(A\cup B\) zbiorów rozłącznych
\(A\) i \(B\), której moc jest równa \(\overline{\overline {A\cup B}}=
\stackrel {=}{A} + \stackrel {=}{B}\).
Przykład
Przeanalizujemy doświadczenie polegające na rzucie monetą i sześcienną kostką do gry oraz wyznaczymy liczbę wszystkich możliwych jego wyników.Oznaczmy zbiór wyników pierwszego etapu doświadczenia, czyli rzutu monetą, przez \(A\), a drugiego, czyli rzutu kostką, przez \(B\). Wtedy \(A=\left\{O,R\right\}\) i \(B=\left\{1,2,3,4,5,6\right\}\). Moce tych zbiorów wynoszą odpowiednio: \(\stackrel{=}{A}\:=2\) i \(\stackrel{=}{B}\:=6\). Zgodnie z regułą mnożenia wszystkich możliwych wyników rzutu kostką i monetą jest \(2\cdot6=12\).
Doświadczenie to można zilustrować za pomocą tabeli lub drzewka.
Tabela w przypadku tego doświadczenia składa się z siedmiu kolumn i trzech wierszy. Pierwsza komórka w pierwszej kolumnie jest pusta, a w pozostałych dwóch komórkach tej kolumny umieszczamy pojedynczo wyniki pierwszego etapu doświadczenia, tzn. elementy zbioru \(A\). Pierwsza komórka w pierwszym wierszu wciąż pozostaje pusta, a w pozostałe komórki tego wiersza wpisujemy wyniki drugiego etapu doświadczenia, tzn. elementy zbioru \(B\). W ten sposób otrzymujemy szkielet tabeli. Puste komórki drugiego i trzeciego wiersza uzupełniamy wynikami całego 2-etapowego doświadczenia w postaci par, w których pierwszy element to wynik pierwszego etapu doświadczenia, a drugi – drugiego. Na przykład w drugim wierszu i trzeciej kolumnie wpiszemy parę \((O,2)\).
W przypadku tabeli liczba wszystkich możliwych wyników odpowiada liczbie par w poniższej tabeli.
| \(\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) |
|---|---|---|---|---|---|---|
| \(O\) | \((O,1)\) | \((O,2)\) | \((O,3)\) | \((O,4)\) | \((O,5)\) | \((O,6)\) |
| \(R\) | \((R,1)\) | \((R,2)\) | \((R,3)\) | \((R,4)\) | \((R,5)\) | \((R,6)\) |
Wykorzystując tak skonstruowane drzewko, liczbę wszystkich możliwych wyników można ustalić, zliczając jego gałęzie albo zliczając elementy znajdujące się na najniższym poziomie rysunku. Gałąź bowiem składa się z dwóch krawędzi, prowadzących od wierzchołka drzewa do jego podstawy, z których każda jest na innym poziomie rysunku.
Wyniki doświadczenia polegającego na rzucie monetą i sześcienną kostką
Odpowiadając na pytanie, ile można stworzyć odwzorowań określonego rodzaju z dostępnych elementów,
trzeba ustalić, jakiego typu jest dane odwzorowanie.
Należy zastanowić się, czy przyporządkowanie korzysta ze wszystkich elementów zbioru, czy mogą się one powtarzać
oraz czy ważna jest ich kolejność. W zależności od ustaleń wyróżniamy trzy rodzaje takich odwzorowań:
permutacje, wariacje i kombinacje. Omówimy te trzy przypadki.
Iloczyn kartezjański zbiorów \(\boldsymbol{A}\) i \(\boldsymbol{B}\)
\[ A\times B =\{(a,b):\ a\in A\ \wedge\ b\in B\} \]
Zbiory \(A\) i \(B\) nazywamy rozłącznymi, jeżeli \[A\cap B=\emptyset\]
Mocą zbioru skończonego \(A\) nazywamy liczbę jego elementów i oznaczamy symbolem \(\overset{=}{A}\).