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.

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.
Wyniki doświadczenia polegającego na rzucie sześcienną kostką i monetą
\(\) \(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)\)
Rysowanie drzewka rozpoczynamy od wierzchołka, z którego wychodzą dwie krawędzie oznaczające wyniki pierwszego etapu doświadczenia, tzn. elementy zbioru \(A\). Następny poziom drzewka to dwie wiązki po sześć krawędzi odpowiadające wynikom drugiego etapu doświadczenia, tzn. elementy zbioru \(B\).
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.
Drzewko przedstawiające wszystkie możliwe wyniki omawianego doświadczenia losowego
Wyniki doświadczenia polegającego na rzucie monetą i sześcienną kostką
Ilustracja graficzna twierdzenia o mnożeniu jest przejrzysta, jednak dla dużych \(n\) rysowanie takiej tabeli czy drzewka jest uciążliwe.

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}\).