Wiemy już, że dowolny zbiór \( n \)-elementowy ma dokładnie \( 2^n \) podzbiorów. Teraz zajmiemy się pytaniem ile taki zbiór ma podzbiorów o dokładnie \( k \) elementach. Policzymy zatem liczność rodziny \( k \)-elemetowych podzbiorów zbioru \( X \). Rodzinę tę oznaczać będziemy przez \( {\mathcal P}_k(X) \).
Współczynnik dwumianowy \( {n \choose k} \) to liczba \( k \)-elementowych podzbiorów zbioru \( n \)-elementowego, tzn. \(\ {n \choose k} = \vert {\mathcal P}_k (\mathbb{Z}_n)\vert \). Wyrażenie \( {n \choose k} \) czytamy \( n \) po \( k \).
Prawdopodobnie jako pierwszy tej notacji użył Andreas von Ettingshausen w 1826. Jednak liczby te już wcześniej pojawiały się wielokrotnie, choćby w Trójkącie Pascala. Sama nazwa "współczynniki dwumianowe" bierze się stąd, że liczby te pojawiają się w rozwinięciu dwumianu \( (x+y)^n \). Zobaczymy to dokładnie w Twierdzeniu 5.7
Przykład
Aby policzyć \( {4\choose 2} \) wypiszmy wszystkie \( 2 \)-elementowe podzbiory \( 4 \) -elementowego zbioru \( \mathbb{Z}_4=\{0,1,2,3\} \). Sa to \(\{0,1\} \), \( \{0,2\} \), \( \{0,3\} \), \( \{1,2\} \), \(\{1,3\} \), \( \{2,3\} \),
skąd \( {4 \choose 2}=6 \).
Bezpośrednio z definicji liczb \( {n\choose k} \) dostajemy:
Obserwacja 5.1
Dla \( n,k \in \mathbb {R} \) zachodzi:
Dowód
Pierwszy punkt jest natychmiastową konsekwencją faktu, że dowolny zbiór \( n \)-elementowy ma tylko jeden \( 0 \)-elementowy podzbiór -podzbiór pusty i tylko jeden podzbiór \( n \)-elementowy - cały zbiór.
Drugi punkt jest oczywisty, jako że zbiór \( n \)-elementowy nie może mieć podzbiorów o \( k>n \) elementach.
Dla dowodu trzeciego punktu, zauważmy jedynie, że podzbiorów jednoelementowych jest dokładnie tyle ile elementów w zbiorze.
Wreszcie dla dowodu ostatniego punktu załóżmy, że \( |{X}|=n\geq k\geq 0 \). Wtedy funkcja
\( {\mathcal P}_k(X)\ni A \mapsto X\setminus A \in {\mathcal P}_{n-k}(X) \)
jest bijekcją. A zatem istotnie \( {n\choose k}={n\choose n-k} \).
Nasza następna obserwacja stanowi fundament dla rekurencyjnej procedury obliczania współczynników dwumianowych.
Obserwacja 5.2
Dla \( 0 < k\leq n \) mamy:
\( {n\choose k}={n-1\choose k-1}+{n-1\choose k}. \)
Dowód
Podobnie jak przy budowaniu zależności rekurencyjnej przy zliczaniu wszystkich podzbiorów zbioru \( n \)-elementowego załóżmy, że \( |{Z}|=n \). Wtedy, po usunięciu ze zbioru \( Z \) elementu \( a\in Z \) dostajemy \( (n-1) \)-elementowy zbiór \( Z' \). Oczywiście wszystkie \( k \)-elementowe podzbiory zbioru \( Z \) można podzielić na dwa typy:
W drugim przypadku są to \( k \)-elementowe podzbiory \( (n-1) \)-elementowego zbioru \( Z' \). Jest więc ich dokładnie \( {n-1 \choose k} \).
Każdy zaś podzbiór pierwszego typu, czyli \( A \in {\mathcal P}_k(Z) \) takie, że \( a\in A \) jest jednoznacznie wyznaczony przez swoje pozostałe \( k-1 \) elementów, czyli \( A=A'\cup \{a\} \) dla pewnego \( A' \in {\mathcal P}_{k-1}(Z') \). A zatem
\( {n \choose k} = {|{\mathcal P}_k(Z)|} = {|{\mathcal P}_k(Z')|} + {|{\mathcal P}_{k-1}(Z')|} = {n-1\choose k}+{n-1\choose k-1}. \)
Trójkąt Pascala (nazwany na cześć Blaise'a Pascala, który napisał znakomitą rozprawę o współczynnikach dwumianowych) bazuje na własności \( {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} \) i ustawia liczby w następujący sposób:
\( n=0,1,2,\ldots \),
Są to kolejno \( {n \choose 0}, {n \choose 1}, {n \choose 2},\ldots, {n \choose n-1},{n \choose n} \)
| \( 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 \) | ||||||
| \( 5\choose 0 \) | \( 5\choose 1 \) | \( 5\choose 2 \) | \( 5\choose 3 \) | \( 5\choose 4 \) | \( 5\choose 5 \) | |||||
| ... | ... | ... | ... | ... | ||||||
Przesunięcie w wierszach, pozwala wyliczyć \( {n \choose k} \) jako sumę \( {n-1 \choose k-1} + {n-1 \choose k} \) dwu liczb stojących bezpośrednio nad \( {n \choose k} \):
Przykład
Napisz program drukujący trójkąt Pascala, ale z liczbami \( {n \choose k} \) modulo \( 2 \), tzn. w miejsce \( {n \choose k} \) wstaw jedynie resztę \( 0 \) lub \( 1 \) z dzielenia liczby \( {n \choose k} \) przez \( 2 \). Zaobserwuj na wydruku powstały fraktal. Wyjaśnij dlaczego tak się dzieje.
W trójkącie Pascala współczynniki o tym samym górnym indeksie, np.
\( \langle {4\choose 0},{4\choose 1},{4\choose 2},{4\choose 3},{4\choose 4} \rangle = \langle {1,4,6,4,1} \rangle \)
tworzą wiersz; natomiast współczynniki o ustalonym dolnym indeksie, np.
\( \langle {5\choose 5},{6\choose 5},{7\choose 5},{8\choose 5},{\ldots} \rangle = \langle {1,6,21,56,}{\ldots} \rangle \)
tworzą przekątną.
Trójkat Pascala ma zera na obrzeżach, a jego wiersze są symetryczne względem pionowej osi przebiegającej przez środek trójkąta. Jest to konsekwencja Obserwacji 5.1. Współczynniki dwumianowe spełniają bardzo wiele ciekawych zależności. Wymienimy tylko te najważniejsze. Zaczniemy od wzoru w postaci zwartej.
Obserwacja 5.3
Dla dowolnych \( 0\leq k\leq n \)
\( {n\choose k}=\frac{n!}{(n-k)!k!}. \)
Dowód
Podamy dwa dowody: kombinatoryczny i indukcyjny.
Dowód kombinatoryczny. Ustalmy pewien \( n \)-elementowy zbiór \( X \), i wybierajmy po kolei \( k \) różnych jego elementów, tzn. utwórzmy injekcję \( \mathbb{Z}_k X \). Z wykładu o zliczaniu zbiorów i funkcji wiemy, ze takich injekcji jest \( \frac{n!}{(n-k)!} \). W wyniku takiego wyboru, dostajemy wszakże pewien uporządkowany ciąg \( k \) elementów zbioru \( X \). Wiele takich ciągów wyznacza ten sam \( k \)-elementowy podzbiór zbioru \( X \). Ciągi takie różnią sie jedynie kolejnością elementów, a zatem jest ich tyle ile permutacji zbioru \( k \)-elemetowego, czyli \( k! \). Zatem jest dokładnie
\( \frac{n(n-1)\cdot\ldots\cdot(n-k+1)}{k!}=\frac{n!}{(n-k)!k!} \)
podzbiorów \( k \)-elementowych zbioru \( n \)-elementowego.
Dowód indukcyjny. Indukcję poprowadzimy względem górnego indeksu \( n \). Dla \( n=0 \) mamy tylko jeden interesujący nas współczynnik \( {0\choose 0}=1 \), i rzeczywiście \( \frac{0!}{(0-0)!0!}=1 \). Załóżmy zatem, że wszystkie współczynniki w \( n \)-tym wierszu spełniają wzór z tezy i rozważmy \( {n+1\choose k} \) dla \( k\in\{0,\ldots,n+1\} \). Jeśli \( k=0 \) to \( {n+1\choose k}=1=\frac{n!}{(n-0)!0!} \). Załóżmy więc, że \( k>0 \). Wtedy:
\( \begin{align*}{n+1\choose k} & ={n\choose k-1}+{n\choose k} \\ & =\frac{n!}{(n-k+1)!(k-1)!}+\frac{n!}{(n-k)!k!} \\ & =\frac{n!}{(n-k)!(k-1)!}\cdot(\frac{1}{n-k+1}+\frac{1}{k}) \\ & =\frac{n!}{(n-k)!(k-1)!}\cdot\frac{k+(n-k+1)}{(n-k+1)k} \\ & =\frac{(n+1)!}{(n-k+1)!k!}. \end{align*} \)
Przykład
\( {15\choose 3}=\frac{15!}{(15-3)!3!}=\frac{13\cdot14\cdot15}{2\cdot3}=13\cdot7\cdot5=455. \)
Przykład
Wyobraźmy sobie, że znajdujemy się w mieście zbudowanym na planie prostopadle przecinających się ulic. Powiedzmy, że znajdujemy się w punkcie \( A \) i chcemy dojść do punktu \( B \), tak jak zaznaczono na rysunku.
Łatwo zauważyć, że jest wiele najkrótszych dróg prowadzących z \( A \) do \( B \). Dla przykładu: możemy pójść \( 3 \) razy na północ i potem cały czas na wschód, ale także możemy iść najpierw \( 6 \) razy na na wschód i dopiero wtedy skręcić na północ.
Ile jest najkrótszych dróg z \( A \) do \( B \)?
Zauważmy, że każda najkrótsza droga biegnie przez dokładnie \( 9 \) skrzyżowań (licząc skrzyżowanie w punkcie \( A \) i nie licząc skrzyżowania w punkcie \( B \)). Na każdym takim skrzyżowaniu musimy podjąć decyzję, czy pójść na wschód czy na północ, przy czym musimy iść dokładnie \( 3 \) razy na północ i dokładnie \( 6 \) razy na wschód.
Zatem liczba najkrótszych dróg z \( A \) do \( B \) to liczba wyborów spośród \( 9 \) skrzyżowań, trzech, na których pójdziemy na północ, bądź \( 6 \) na których pójdziemy na wschód. A zatem liczba ta wynosi \( {9\choose 3}={9\choose 6}=94 \).
W ogólności załóżmy, że mamy kratkę \( m\times n \) i chcemy narysować najkrótszą łamaną po krawędziach kratki łączącą lewy dolny wierzchołek z prawym górnym. Na ile sposobów możemy narysować taką łamaną?
Widzimy, że musimy narysować \( m+n \) odcinków jednostkowych, z których dokładnie \( m \) jest pionowych i dokładnie \( n \) jest poziomych. Zatem jest
\( {m+n\choose m}={m+n\choose n}=\frac{(m+n)!}{m!n!} \)
sposobów połączenia dwóch przeciwległych wierzchołków.
Przykład
Ile rozwiązań ma równanie
\( x_0+x_1+x_2+x_3+x_4=7, \)
gdzie \( x_i \) są liczbami naturalnymi?
Użyjmy kratki rozważanej w poprzednim przykładzie do połączenia przeciwległych jej rogów. W kratce rozmiaru \( 4\times7 \) suma poziomych odcinków daje \( 7 \) i jest dokładnie \( 5 \) takich odcinków, po jednym na każdym poziomie. Jeśli długości tych odcinków oznaczymy odpowiednio przez \( x_0,x_1,x_2,x_3,x_4 \), to każda taka droga (łamana) na kratce ustala pewne rozwiązanie naszego równania, i każde rozwiązanie równania wyznacza dokładnie jedna drogę (łamaną). Dla przykładu - animacja obok.
Zatem istnieje \( {7+4\choose 4}=330 \) rozwiązań naszego równania.
W ogólności, równanie
\( x_0+x_1+\ldots+x_{k-1}=n, \)
ma dokładnie tyle rozwiązań w liczbach naturalnych gdzie \( x_i \), ile jest łamanych w kratce \( k \times n \), czyli \( {n+k-1\choose n}={n+k-1\choose k-1} \).
Przykład
Ile rozwiązań ma równanie
\( x_0+\ldots+x_{k-1}=n, \)
gdzie \( x_i \) są dodatnimi liczbami naturalnymi?
Zauważmy, że każde rozwiązanie tego równania z warunkami \( x_i\geq 1 \), można otrzymać z rozwiązania w liczbach naturalnych równania
\( y_0+\ldots+y_{k-1}=n-k, \)
poprzez podstawienie \( x_i=y_i+1 \). Na podstawie poprzedniego przykładu poszukiwanych rozwiązań jest zatem \( n-1 \choose k-1 \). Rozważmy \( n \) obiektów (np. punktów) ustawionych w ciągu jeden przy drugim.
Separatorem nazywamy pionową kreskę położoną pomiędzy dwoma punktami. Zatem pomiędzy \( n \) punktami mamy \( n-1 \) możliwych pozycji dla separatora. Zauważmy, że każde rozwiązanie naszego równania jednoznacznie odpowiada jednemu z możliwych rozmieszczeń \( k-1 \) separatorów wśród \( n-1 \) pozycji. Liczba punktów do pierwszego separatora to wartość \( x_0 \), liczba punktów pomiędzy pierwszym a drugim separatorem to \( x_1 \), itd., liczba punktów za ostatnim \( k-1 \)-szym separatorem to \( x_{k-1} \). Dla przykładu:
Na odwrót każde rozwiązanie \( x_0,x_1,\ldots,x_{k-1} \) naszego równania wyznacza jednoznacznie rozłożenie \( k-1 \) separatorów: pierwszy kładziemy po \( x_0 \) punktach, drugi po \( x_0+x_1 \), itd. Zatem liczba rozwiązań naszego równania to liczba rozmieszczeń \( k-1 \) separatorów na \( n-1 \) pozycjach, czyli \( {n-1\choose k-1} \).
Przykład
Rozważmy znów kratkę, tym razem kwadratową, wielkości \( n\times n \), i policzmy na ile sposobów można w jej wnętrzu narysować prostokąt tak, aby wszystkie jego boki były równoległe do krawędzi kratki?
Zauważmy, że każdy taki prostokąt jest jednoznacznie wyznaczony przez dwie linie poziome (spośród \( n+1 \)) oraz dwie linie pionowe (znów spośród \( n+1 \)). Rzeczywiście, dowolny prostokąt wyznacza dwie linie poziome i dwie pionowe (te przylegające do jego boków). I na odwrót dowolny wybór linii pozwoli nam nakreślić jednoznacznie prostokąt w kratce.
Poziome linie możemy wybrać na \( {n+1\choose 2} \) sposobów i pionowe linie także na \( {n+1\choose 2} \) sposobów. Zatem prostokąt w kratce \( n\times n \) możemy narysować na dokładnie
\( {n+1\choose 2}^2=(\frac{n(n+1)}{2})^2 \)
sposobów. W przykładowej kratce na rysunku wymiarów \( 5\times 5 \) możemy więc umieścić \( (\frac{5(5+1)}{2})^2=225 \) prostokątów.
Przechodzimy teraz do kolejnych własności współczynników dwumianowych. Rozpoczniemy od sumowania liczb na przekątnej trójkąta Pascala. Przekątna taka jest oczywiście nieskończona - sumujemy więc tylko jej początkowy fragment.
Obserwacja 5.4 [reguła sumowania po górnym indeksie]
Dla \( n,k\in \mathbb{N} \) mamy
\( \displaystyle \sum_{i=0}^{n}{i\choose k}={n+1\choose k+1}. \)
Dowód
Ustalmy \( (n+1) \)-elementowy zbiór \( X=\{x_0,\ldots,x_n\} \) Rozważając jego \( (k+1) \)-elementowe podzbiory zwracamy uwagę na element tego podzbioru, który ma największy indeks. Oczywiście jest \( i\geq k \), gdyż \( X=\{x_0,\ldots,x_{k-1}\} \) nie ma \( (k+1) \)-elementowych podzbiorów. Równie łatwo jest zauważyć, że jest dokładnie jeden podzbiór \( (k+1) \)-elementowy w którym \( x_{k} \) jest elementem o najwyższym indeksie, jest to zbiór \( \{x_0,\ldots,x_{k-1}\} \).
Policzmy teraz podzbiory zbioru \( X \), w których \( x_i \) jest elementem o największym indeksie, przy czym \( i>k \). Oprócz elementu \( x_i \) każdy taki zbiór ma dokładnie \( k \) elementów wybranych z \( i \)-elementowego zbioru \( \{x_0,\ldots,x_{i-1}\} \). Wyboru tych elementów można dokonać na \( {i\choose k} \) sposobów. Zatem podzbiorów zbioru \( X \), w których \( x_i \) jest elementem o największym indeksie jest dokładnie \( {i\choose k} \). Sumując po wszystkich możliwych \( i \), czyli \( i\in\{k,\ldots,n\} \) otrzymujemy:
\( \displaystyle \sum_{i=0}^n{i\choose k}=\sum_{i=k}^n{i\choose k}={n+1\choose k+1}. \)
Podobnie możemy sumować liczby położone na linii "prostopadłej" do przekątnych Trójkąta Pascala, czyli liczby postaci \( {n+i\choose i} \).
Obserwacja 5.5 [reguła sumowania równoległego] Dla \( n,k\in\mathbb{N} \) mamy:
\( \displaystyle \sum_{i=0}^{k}{n+i\choose i}={n+k+1\choose k}. \)
Dowód
Tożsamość tę udowodnimy wykorzystując dwukrotnie {regułę symetrii} oraz {regułę sumowania po górnym indeksie}:
\( \begin{align*}\sum_{i=0}^{k}{n+i\choose i} & =\sum_{i=0}^k{n+i\choose (n+i)-i} =\sum_{i=0}^k{n+i\choose n} =\sum_{i=n}^{n+k}{i\choose n} \\ & ={n+k+1\choose n+1}={n+k+1\choose k}. \end{align*} \)
Obserwacja 5.6 [tożsamość Cauchy'ego, splot Vandermonde'a]
Dla liczb naturalnych \( m,n,k \) mamy:
\( \displaystyle \sum_{i=0}^k{m\choose i}{n\choose k-i}={m+n\choose k}. \)
Dowód
Policzymy liczbę wszystkich wyborów \( k \) osób z grona \( m \) mężczyzn i \( n \) kobiet, czyli liczbę \( {m+n\choose k} \) na jeszcze jeden sposób. Wybierając \( k \) osób wybieramy najpierw \( i \) mężczyzn na \( {m\choose i} \) sposobów, a potem \( k-i \) kobiet na \( {n\choose k-i} \) sposobów. Pozostaje teraz zsumować po wszystkich możliwych wartościach parametru \( i \).