matematyka : Podstawowe pojęcia

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.

Twierdzenie (reguła mnożenia)

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}$ .

Twierdzenie (reguła dodawania)

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}$ .