Podzbiory zbioru skończonego

W tym rozdziale zajmiemy się zliczaniem różnych podzbiorów zbioru skończongo.

Liczba wszystkich podzbiorów

Zadanie 1.7.1: Dany jest zbiór n -elementowy A . Ile jest wszystkich podzbiorów zbioru A ?

Wynik uzyskany w zadaniu 1.7.1. jest tak ważny, że sformułujemy go w postaci następującego twierdzenia:

Wykażemy, że zbiór liczb

$\qquad A = \{ 1, 2, 3, \ldots , n\}$

ma 2ⁿ podzbiorów. Wiemy, że istnieje 2ⁿ wariacji n-elementowych z powtórzeniami ze zbioru {0,1} . Taka wariacja jest ciągiem

$\qquad (c_1, c_2, c_3, \ldots , c_ n),$

gdzie każdy wyraz c_k jest równy 0 lub 1. Te wariacje można połączyć w pary z podzbiorami zbioru A. Mianowicie, wariację

$\qquad (c_1, c_2, c_3, \ldots , c_ n)$

łączymy w jedną parę ze zbiorem

$\qquad \{ k\in \mathbb {N}: 1 \le k \le n \, \land \, c_ k=1\} ,$

czyli ze zbiorem numerów tych miejsc, na których w danej wariacji stoi jedynka.

Popatrzmy na przykład. Niech n = 6 . Weźmy wariację (1,1,0,1,0,1) . Łączymy ją w parę ze zbiorem {1,2,4,6}: dlatego, że w naszej wariacji na miejscach pierwszym, drugim, czwartym i szóstym stoją jedynki. Cały zbiór {1,2,3,4,5,6} jest połączony w parę z wariacją (1,1,1,1,1,1), a zbiór pusty $\emptyset$ jest połączony w parę z wariacją (0,0,0,0,0,0) .

Łatwo można zauważyć, że łącząc w taki sposób wariacje z podzbiorami zbioru A wykorzystamy wszystkie wariacje i podzbiory zbioru A oraz że każda wariacja i każdy zbiór występują w tylko jednej parze. Wystarczy teraz skorzystać z zasady równoliczności, by stwierdzić, że zbiór $A = \{ 1, 2, 3, \ldots , n\}$ ma 2ⁿ podzbiorów.

Trójkąt Pascala, kombinacje i współczynniki dwumianowe

Teraz zajmiemy się zadaniem wyznaczenia liczby k-elementowych podzbiorów zbio­ru n-elementowego. Popatrzmy najpierw na kilka przykładów. Zbiór pusty ma tylko jeden podzbiór, mianowicie zbiór pusty: $\emptyset$ .

Weźmy teraz zbiór jednoelementowy $A=\{ \clubsuit \}$ . Ma on dwa podzbiory: zbiór pusty (nie mający elementów) i sam zbiór A (mający jeden element). Oto one:

$\qquad \begin{array}{cc} \emptyset \quad & \quad \{ \clubsuit \} \\ \end{array}$

Ćwiczenie. Weź kartkę papieru i wypisz na niej wszystkie pozdbiory zbioru A, który ma

1. dwa elementy,
2. trzy elementy,
3. cztery elementy.

Postępuj systematycznie i wypisuj podzbiory w kolumnach: w pierwszej kolumnie zbiór pusty, w drugiej - podzbiory jednoelementowe, w trzeciej - ...

(Autor tekstu też wykonał tę pracę i opisał jej wyniki - można je zobaczyć).

Weźmy zbiór dwulementowy $A=\{ \clubsuit ,\spadesuit \}$. Ma on cztery podzbiory. Widzimy je wypisane w trzech kolumnach. W pierwszej kolumnie mamy tylko jeden zbiór: zbiór pusty. W drugiej kolumnie mamy dwa podzbiory jednoelementowe. W trzeciej kolumnie mamy też tylko jeden podzbiór: cały zbiór A (mający dwa elementy). Oto te podzbiory:

$\qquad\begin{array}{ccc} \emptyset & \{ \clubsuit \} & \{ \clubsuit ,\spadesuit \} \\ & \{ \spadesuit \} & \\ \end{array}$

Podzbiory zbioru trzyelementowgo $A=\{ \clubsuit ,\spadesuit ,\heartsuit\}$ wypiszemy w czterech kolumnach. W pierwszej, jak zawsze, będzie tylko jeden podzbiór: zbiór pusty. W drugiej będą trzy podzbiory jednolementowe. W trzeciej trzy podzbiory dwuelementowe. Wreszcie w czwartej będzie tylko jeden podzbiór trzylementowy, cały zbiór A :

$\qquad\begin{array}{cccc} \emptyset & \{ \clubsuit \} & \{ \clubsuit ,\spadesuit \} & \{ \clubsuit ,\spadesuit ,\heartsuit \} \\ & \{ \spadesuit \} & \{ \clubsuit ,\heartsuit \} & \\ & \{ \heartsuit \} & \{ \spadesuit ,\heartsuit \} & \\ \end{array}$

Popatrzmy na ostatni przykład. Tym razem niech zbiór A ma cztery elementy:

$A = \{ \clubsuit ,\diamondsuit ,\heartsuit ,\spadesuit \} .$

Jego podzbiory wypiszemy teraz w pięciu kolumnach. W pierwszej będzie tylko zbiór pusty: jedyny podzbiór zeroelementowy. W drugiej będą cztery podzbiory jednoelementowe. W trzeciej będą podzbiory dwuelementowe, w czwartej trzyelementowe i w ostatniej, piątej kolumnie, jeden podzbiór czteroelementowy: cały zbiór A .

$\qquad\begin{array}{lllll} \emptyset & \{ \clubsuit \} & \{ \clubsuit ,\diamondsuit \} & \{ \clubsuit ,\diamondsuit ,\heartsuit \} & \{ \clubsuit ,\diamondsuit ,\heartsuit ,\spadesuit \} \\ & \{ \diamondsuit \} & \{ \clubsuit ,\heartsuit \} & \{ \clubsuit ,\diamondsuit ,\spadesuit \} & \\ & \{ \heartsuit \} & \{ \clubsuit ,\spadesuit \} & \{ \clubsuit ,\heartsuit ,\spadesuit \} & \\ & \{ \spadesuit \} & \{ \diamondsuit ,\heartsuit \} & \{ \diamondsuit ,\heartsuit ,\spadesuit \} & \\ & & \{ \diamondsuit ,\spadesuit \} & & \\ & & \{ \heartsuit ,\spadesuit \} & & \\ \end{array}$

Zapiszmy liczby podzbiorów rozważanych wyżej zbiorów A w tabelce:

$\qquad\begin{array}{ccccccccc}& & & & 1 & & & & \\ & & & 1 & & 1 & & & \\ & & 1 & & 2 & & 1 & & \\ & 1 & & 3 & & 3 & & 1 & \\ 1 & & 4 & & 6 & & 4 & & 1 \\ \end{array}$

Tę tablicę nazywamy trójkątem Pascala, od nazwiska wielkiego filozofa i matematyka francuskiego, żyjącego w XVII wieku. Zauważmy regułę rządzącą liczbami umieszczonymi w trójkącie Pascala: każdy wiersz zaczyna się i kończy jedynką; każda z pozostałych liczb jest sumą liczb stojących bezpośrednio nad nią jeden wiersz wyżej: z lewej i z prawej strony. Na przykład trójka stojąca na drugim miejscu w czwartym wierszu jest sumą jedynki i dwójki z wiersza drugiego, szóstka stojąca w wierszu piątym jest sumą stojących nad nią dwóch trójek w wierszu czwartym itp.

Tę liczbę nazywamy też współczynnikiem dwumianowym , a oznaczający ją symbol nazywamy czasem symbolem Newtona. Nazwa "współczynnik dwumianowy" pochodzi stąd, że te współczynniki pojawiają się w tzw. wzorze dwumianowym Newtona. Każdy k-elementowy podzbiór zbioru n-elementowego nazywamy również k-elementową kombinacją ze zbioru n -elementowego.

Współczynniki dwumianowe są zatem umieszczone w trójkącie Pascala w następujący sposób:

$\qquad\begin{array}{ccccccccc}& & & & {0 \choose 0} & & & & \\ & & & {1 \choose 0} & & {1 \choose 1} & & & \\ & & {2 \choose 0} & & {2 \choose 1} & & {2 \choose 2} & & \\ & {3 \choose 0} & & {3 \choose 1} & & {3 \choose 2} & & {3 \choose 3} & \\ {4 \choose 0} & & {4 \choose 1} & & {4 \choose 2} & & {4 \choose 3} & & {4 \choose 4} \\ & & & & \ldots & & & & \\ \end{array}$

Oczywiście trójkąt Pascala nie kończy się na piątym wierszu: można go przedłużać w dół w nieskończoność.

Zauważmy, że w pierwszym wierszu mamy jeden współczynnik ${0 \choose 0}$ . W drugim wierszu mamy dwa współczynniki ${1 \choose i}$ dla i = 0,1 . W trzecim wierszu mamy trzy współczynniki ${2 \choose i}$ dla i = 0,1,2 i tak dalej.

Na przykład współczynnik ${7 \choose 2}$ stoi na trzecim miejscu w wierszu ósmym, a współczynnik ${{13} \choose 5}$ stoi na miejscu szóstym w wierszu czternastym.

Tę własność można wyrazić nieco inaczej.

Znaczenie liczb n i k we współczynniku dwumianowym ${n \choose k}$ jest następujące:

1. liczba n jest numerem wiersza, w którym umieszczony jest współczynnik ${n \choose k}$ , z tym tylko, że zaczynamy liczenie od zera; jest to przy tym liczba elementów zbioru, którego podzbiory rozpatrujemy;
2. liczba k jest numerem miejsca, na którym w danym wierszu stoi ten współczynnik, z tym, że teraz też zaczynamy liczenie od zera; jest to przy tym liczba elementów podzbiorów, które zliczamy. Liczba k przyjmuje więc wartości od 0 do n .

Regułę rządzącą współczynnikami dwumianowymi, czyli liczbami umieszczonymi w trójkącie Pascala, możemy zapisać w następujący sposób.

Zauważyliśmy już, że ta reguła jest prawdziwa dla $n \le 4$. Czy jednak jest ona prawdziwa także dla większych n ?

Zadanie 1.7.2: Udowodnij, że dla każdego $n \ge 0$ zachodzą równości:
$\qquad {n \choose 0}=1, \quad {n \choose n}=1.$

Zadanie 1.7.3: Udowodnij, że dla każdego $n \ge 2$ i dla każdego k takiego, że $1 \le k < n$ zachodzi równość:
$\qquad {n \choose k} = {{n-1} \choose {k-1}}+{{n-1} \choose k}$

Ten dość formalnie opisany dowód można opowiedzieć nieco prościej.

1. Załóżmy, że wybierzemy wychowawcę. Mamy więc jedną osobę. Pozostałe k − 1 osób musimy dobrać spośród n − 1 uczniów. To możemy zrobić na ${n-1 \choose k-1}$ sposobów, gdyż tyle jest k − 1 -elementowych podzbiorów zbioru n − 1 -elementowego.
2. Załóżmy, że nie wybierzemy wychowawcy. Wtedy wszystkie osoby na wycieczkę musimy wybrać spośród n − 1 uczniów. Możemy to zrobić na ${{n-1} \choose k}$ sposobów, gdyż tyle jest k-elementowych podzbiorów zbioru n − 1-elementowego. Łącznie, dodając te dwie liczby, otrzymamy zatem
   ${{n-1} \choose {k-1}}+{{n-1} \choose k}$
   sposobów wybrania osób na wycieczkę. A więc ta liczba musi być równa ${n \choose k}$, co dowodzi równości
   ${n \choose k} = {{n-1} \choose {k-1}}+{{n-1} \choose k}.$

Taki sposób dowodzenia twierdzeń kombinatorycznych nosi nazwę dowodu kombinatorycznego . Polega on na tym, by elementy pewnego zbioru policzyć dwiema różnymi metodami. Otrzymamy dwie liczby: muszą one być równe, gdyż liczba elementów zbioru nie zależy od sposobu liczenia. W tym i następnym rozdziale zobaczymy jeszcze kilka podobnych dowodów kombinatorycznych.

Współczynniki dwumianowe i silnie

Mamy metodę znajdowania liczb ${n \choose k}$. Wystarczy wypisać n + 1 wierszy trójkąta Pascala i następnie znaleźć liczbę stojącą w tym wierszu na miejscu k + 1 . Jest to jednak dość kłopotliwe i przydałby się wzór, za pomocą którego moglibyśmy obliczać współczynniki dwumianowe. Taki wzór istnieje i spróbujemy go teraz wyprowadzić.

Zadanie 1.7.4: Udowodnij, że jeśli $0 \le k \le n$ , to

$\qquad{n \choose k} = \frac{n! }{ k! \cdot (n-k)!}$

Zadanie 1.7.5: Udowodnij, że jeśli $1 \le k \le n$ , to liczba $n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)$ dzieli się bez reszty przez k! .

Treść zadania 1.7.5. można wypowiedzieć w następujący sposób: iloczyn k kolejnych liczb naturalnych dzieli się bez reszty przez k!. Na przykład, iloczyn trzech kolejnych liczb naturalnych dzieli się bez reszty przez 3!, czyli przez 6; iloczyn czterech kolejnych liczb naturalnych dzieli się bez reszty przez 24; iloczyn pięciu kolejnych liczb naturalnych dzieli się bez reszty przez 120 i tak dalej.

Każdą z tych własności z osobna można dość łatwo udowodnić bezpośrednio. Na przykład, wśród trzech kolejnych liczb naturalnych znajduje się co najmniej jedna liczba parzysta i dokładnie jedna liczba podzielna przez 3, iloczyn tych liczb dzieli się zatem przez $2 \cdot 3 = 6$ (bo liczby 2 i 3 są względnie pierwsze). Jednak dowód bezpośredni dla dowolnego n nie jest już tak prosty jak dowód kombinatoryczny.