Wiemy już, że dowolny zbiór n-elementowy ma dokładnie 2n 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 Pk(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 .