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 ?
\(A = \{ a_1, a_2, a_3, \ldots , a_ n\} .\)
Zastanówmy się, w jaki sposób można otrzymać dowolny podzbiór zbioru A . Wykonajmy n czynności. Na początku zdecydujmy, czy do naszego podzbioru zaliczymy element a1 . Mamy dwie możliwości. Druga czynność polega na zdecydowaniu, czy do naszego podzbioru zaliczymy element a2 . I tu mamy dwie możliwości. Trzecią czynnością będzie zdecydowanie, czy zaliczymy element a3 i tak dalej. Każda czynność daje jeden z dwóch możliwych wyników: odpowiedź "tak, zaliczamy" lub odpowiedź "nie, nie zaliczamy". Reguła mnożenia mówi nam, że łącznie mamy
\(\underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n} = 2^ n\)
możliwości podania tych n odpowiedzi. Każda z tych możliwości określa jeden podzbiór zbioru A . Istnieje zatem 2n podzbiorów zbioru n-elementowego.
∎
Wynik uzyskany w zadaniu 1.7.1. jest tak ważny, że sformułujemy go w postaci następującego twierdzenia:
| Twierdzenie 1.7.1: |
|
Zbiór n-elementowy ma 2n podzbiorów. |
Wykażemy, że zbiór liczb
\(\qquad A = \{ 1, 2, 3, \ldots , n\}\)
ma 2n podzbiorów. Wiemy, że istnieje 2n 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 ck 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 2n podzbiorów.
Trójkąt Pascala, kombinacje i współczynniki dwumianowe
Teraz zajmiemy się zadaniem wyznaczenia liczby k-elementowych podzbiorów zbioru 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
- dwa elementy,
- trzy elementy,
- 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.
|
Liczbę k -elementowych podzbiorów zbioru n-elementowego będziemy oznaczać symbolem \(\qquad {n \choose k}.\) (Czytamy: "n nad k" lub "n po k").
|
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.
|
Ogólna reguła: współczynnik dwumianowy \({n \choose k}\) stoi w trójkącie Pascala w wierszu n + 1, na miejscu k + 1.
|
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:
- 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;
- 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.
|
Reguła tworzenia wierszy trójkąta Pascala 1. Każdy wiersz zaczyna się i kończy jedynką: \(\qquad {n \choose 0}=1, \quad {n \choose n}=1.\) 2. Każdy z pozostałych wyrazów jest sumą wyrazów stojących nad nim jeden wiersz wyżej: \(\qquad {n \choose k} = {{n-1} \choose {k-1}}+{{n-1} \choose k} \) dla k spełniających nierówności 0 < k < n.
|
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}\)
\({n \choose k} = {{n-1} \choose {k-1}}+{{n-1} \choose k}.\)
mamy liczbę k -elementowych podzbiorów zbioru A. Oznaczmy przez X zbiór wszystkich k -elementowych podzbiorów zbioru A . Ponieważ \(n \ge 1\) , więc zbiór A jest niepusty. Wybierzmy pewien element a zbioru A :
\(a \in A.\)
Podzbiory zbioru A należące do zbioru X podzielimy na dwa zbiory. Do pierwszego zaliczymy te podzbiory, których elementem jest a, do drugiego zaliczymy te podzbiory, do których a nie należy:
\(\begin{array}{c} Y = \{ B \in X:\, a \in B\} , \\ Z = \{ B \in X:\, a \not\in B\} . \\ \end{array}\)
Oczywiście zbiory Y i Z są rozłączne. Jeśli bowiem podzbiór B zbioru A należy do X, to albo a należy do B i wtedy \(B\in Y\), albo a nie należy do B i wtedy \(B \in Z\) . Zatem
| X | = | Y | + | Z | .
Wiemy z definicji zbioru X , że
\(|X| = {n \choose k}.\)
A ile elementów mają zbiory Y i Z? Zajmiemy się najpierw zbiorem Z . Jeśli \(B \in Z\) , to B jest k -elementowym podzbiorem zbioru A i element a nie należy do B. Zatem B jest k -elementowym podzbiorem zbioru A , z którego wyrzucono element a , czyli zbioru \(A\setminus \{ a\}\) . Oczywiście istnieje \({{n-1} \choose k}\) takich podzbiorów B , bo tyle jest k -elementowych podzbiorów (n − 1) -elementowego zbioru \(A\setminus \{ a\}\) . Zatem
\(|Z| = {{n-1} \choose k}.\)
Teraz przyjrzyjmy się zbiorowi Y. Do tego zbioru należą te podzbiory B zbioru A, w których jest element a. Taki podzbiór B ma zatem postać
\(B=\{ a\} \cup B',\)
gdzie B' jest (k − 1)-elementowym podzbiorem zbioru \(A\setminus \{ a\}\) . Ponieważ liczba takich podzbiorów B' jest równa \({{n-1} \choose {k-1}}\), więc
\(|Y| = {{n-1} \choose {k-1}}.\)
Podstawiając obliczone liczby | X | , | Y | i | Z | do równości
| X | = | Y | + | Z |
otrzymujemy ostatecznie równość
\({n \choose k} = {{n-1} \choose {k-1}}+{{n-1} \choose k}.\)
∎
Ten dość formalnie opisany dowód można opowiedzieć nieco prościej.
- 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.
- 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)!}\)
\(\frac{n! }{ (n-k)!}.\)
Popatrzmy teraz, na ile sposobów możemy wybrać taką wariację. Wykonujemy dwie czynności. Pierwsza z nich polega na wybraniu k elementów spośród danych n elementów, druga czynność polega na ustawieniu wybranych elementów w ciąg tworzący naszą wariację. Pierwsza czynność daje jeden z \({n \choose k}\) wyników, bo tyle jest k -elementowych podzbiorów zbioru n -elementowego. Druga czynność, niezależnie od wyniku pierwszej, może być wykonana na k! sposobów, gdyż tyle jest permutacji zbioru k -elementowego, tzn. na tyle sposobów można uporządkować k elementów. Z reguły mnożenia wynika, że
\(\frac{n! }{ (n-k)!} = {n \choose k} \cdot k!,\)
czyli
\({n \choose k} = \frac{n! }{ k! (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! .
\(n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1) = \frac{n! }{ (n-k)!} = {n \choose k} \cdot 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.