Matematyka dyskretna 1/Wykład 5: Współczynniki dwumianowe

Zliczanie podzbiorów raz jeszcze

Andreas Freiherr von Ettingshausen (1796-1878)
Zobacz biografię

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}={|{\mathcal {P}}_{k}(\mathbb {Z} _{n})|}$. 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:

• ${n \choose 0}={n \choose n}=1$,

• ${n \choose k}=0$, dla $k>n$,

• ${n \choose 1}=n$, dla $n>0$,

• ${n \choose k}={n \choose n-k}$, dla $n\geqslant k\geqslant 0$.

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\geqslant k\geqslant 0$. Wtedy funkcja

${\mathcal {P}}_{k}(X)\ni A\mapsto XminusA\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\leqslant 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:

• albo mają w sobie element $a$,

• albo go nie mają.

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

Blaise Pascal (1623-1662)
Zobacz biografię

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:

• wiersze trójkąta numerowane są kolejnymi liczbami naturalnymi
  

$n=0,1,2,\ldots$,

• w każdym wierszy trójkąta występuje dokładnie $n+1$ liczb.
  

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

<flashwrap>file=Trojkat pascala.swf|size=large</flashwrap>

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.

$\left\langle {4 \choose 0},{4 \choose 1},{4 \choose 2},{4 \choose 3},{4 \choose 4}\right\rangle =\left\langle {1,4,6,4,1}\right\rangle$

tworzą wiersz; natomiast współczynniki o ustalonym dolnym indeksie, np.

$\left\langle {5 \choose 5},{6 \choose 5},{7 \choose 5},{8 \choose 5},{\ldots }\right\rangle =\left\langle {1,6,21,56,\ldots }\right\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\leqslant k\leqslant 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{aligned}{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 \left({\frac {1}{n-k+1}}+{\frac {1}{k}}\right)\\&={\frac {n!}{(n-k)!(k-1)!}}\cdot {\frac {k+(n-k+1)}{(n-k+1)k}}\\&={\frac {(n+1)!}{(n-k+1)!k!}}.\end{aligned}}$

Przykład

${15 \choose 3}={\frac {15!}{(15-3)!3!}}={\frac {13\cdot 14\cdot 15}{2\cdot 3}}=13\cdot 7\cdot 5=455.$

MD1-4.2.swf

MD1-4.3.swf

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.

4.4-4.5.swf

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

SW 6.1.swf

SW 6.2.swf

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

MD1-4.11.swf

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}=\left({\frac {n(n+1)}{2}}\right)^{2}$

sposobów. W przykładowej kratce na rysunku wymiarów $5\times 5$ możemy więc umieścić $\left({\frac {5(5+1)}{2}}\right)^{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.

Plik:4.6.mp4

4.6.swf

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

Plik:4.7.mp4

4.7.swf

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{aligned}\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{aligned}}$

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

Dwumiany

Poniższe Twierdzenie o Dwumianie wyjaśnia pochodzenie tajemniczej nazwy "współczynniki dwumianowe". Twierdzenie to często przypisuje się Pascalowi. Tymczasem było ono już znane indyjskiemu matematykowi Pingala w III wieku p.n.e..

Obserwacja 5.7 [Twierdzenie o Dwumianie]

Dla $x,y\in \mathbb {R}$ i $n\in \mathbb {N}$

$\displaystyle (x+y)^{n}=\sum _{i=0}^{n}{n \choose i}x^{i}y^{n-i}.$

Dowód

Przedstawmy najpierw potęgę $(x+y)^{n}$ w rozwiniętej formie iloczynu:

$\underbrace {(x+y)\cdot \ldots \cdot (x+y)} _{n\ razy}.$

Korzystając z rozdzielności mnożenia, wyrażenie to staje się sumą składników. Każdy taki składnik to iloczyn pewnej liczby $x$-ów i pewnej liczby $y$-ów, przy czym łącznie iloczyn taki ma $n$ czynników. A zatem każdy składnik ma postać $x^{k}y^{n-k}$. Powstaje on poprzez wybór $k$ (spośród $n$) czynników w iloczynie $(x+y)\cdot \ldots \cdot (x+y)$, z których do składnika postaci $x^{k}y^{n-k}$ wchodzi $x$ (a tym samym $(n-k)$ składników, z których wchodzi $y$). Tym samym składników postaci $x^{k}y^{n-k}$ jest tyle, ile $k$-elementowych podzbiorów zbioru $n$-elementowego, czyli $x^{k}y^{n-k}$ pojawi się w sumie ${n \choose k}$-krotnie.

Twierdzenie o Dwumianie można też udowodnić za pomocą indukcji, co pozostawiamy jako ćwiczenie.

Przykład

${\begin{aligned}(a+b)^{2}&=a^{2}+2ab+b^{2},\\(a+b)^{3}&=a^{3}+3a^{2}b+3ab^{2}+b^{3},\\(a+b)^{4}&=a^{4}+4a^{3}b+6a^{2}b^{2}+4ab^{3}+b^{4}.\end{aligned}}$

MD1-4.8.swf

Wniosek 5.8

Dla dowolnego $n\geqslant 0$

• $(1+x)^{n}=\sum _{i=0}^{n}{n \choose i}x^{i}$,

• ${n \choose 0}+{n \choose 1}+\ldots +{n \choose n}=2^{n}$,

• ${n \choose 0}-{n \choose 1}+\ldots +(-1)^{n}{n \choose n}=0^{n}$. (Uwaga: ${0 \choose 0}=1=0^{0}$)

Dowód

Wszystkie punkty wynikają trywialnie z Twierdzenia o Dwumianie. (Pierwszy jest oczywisty. Dla dwu pozostałych zauważmy jedynie, że $(1+1)^{n}=2^{n}$, $(1-1)^{n}=0$.) Jednak drugi i trzeci punkt mają ładną interpretację kombinatoryczną.

Istotnie, liczba podzbiorów zbiorów $n$ elementowego to $2^{n}$. Z drugiej strony licząc te podzbiory, możemy kolejno zliczać podzbiory $0,1,2,\ldots$-elementowe - jest ich ${n \choose 0},{n \choose 1},{n \choose 2},\ldots$.

Nieco dłuższy jest argument kombinatoryczny dla naprzemiennej sumy ${n \choose 0}-{n \choose 1}+\ldots +(-1)^{n}{n \choose n}=0$. Dla $n=0$ jest to oczywiste. Natomiast dla $n>0$ jest to równoważne stwierdzeniu, że dla $n$-elementowego zbioru $X$

• liczba podzbiorów zbioru $X$ o parzystej liczbie elementów jest równa liczbie podzbiorów $X$ o nieparzystej liczbie elementów.

Załóżmy najpierw, że $n$ jest nieparzyste. Wtedy każdy podzbiór zbioru $X$ o parzystej liczbie elementów ma dopełnienie o nieparzystej liczbie elementów, a każdy podzbiór zbioru $X$ o nieparzystej liczbie elementów ma dopełnienie o parzystej liczbie elementów. Ta bijektywna odpowiedniość dowodzi, że w istocie jest ich tyle samo.

Załóżmy zatem, że $n$ jest parzyste i ustalmy $x\in X$. Zdefiniujmy funkcję $f:{\mathcal {P}}(X){\mathcal {P}}(X)$, kładąc

$f(Y)={\begin{cases}(X-Y)-\{x\}&{\mbox{, jeśli }}{x}\not \in {Y}\subseteq {X}\\(X-Y)\cup \{x\}&{\mbox{, jeśli }}{x}\in {Y}\subseteq {X}.\end{cases}}$

Zauważmy, że $f$ jest permutacją ${\mathcal {P}}(X)$. Rzeczywiście, dla różnych podzbiorów $Y_{1},Y_{2}\subseteq X$ mamy:

• jeśli $x\notin Y_{1}$ i $x\notin Y_{2}$ to

$f(Y_{1})=(X-Y_{1})-\{x\}=X-Y_{1}\neq X-Y_{2}=(X-Y_{2})-\{x\}=f(Y_{2}),$

• jeśli $x\in Y_{1}$ i $x\in Y_{2}$ to

$f(Y_{1})=(X-Y_{1})\cup \{x\}\neq (X-Y_{1})\cup \{x\}=f(Y_{2}),$

• jeśli $x\in Y_{1}$ i $x\notin Y_{2}$ to $x\in f(Y_{1})$ i $x\notin f(Y_{2})$, zatem $f(Y_{1})\neq f(Y_{2})$.

To dowodzi, że $f$ jest injekcją. Dla dowodu surjektywności weźmy dowolne $Z\subseteq X$. Jeśli $x\in Z$ to $f((X-Z)\cup \{x\})=Z$, jeśli zaś $x\notin Z$ to $f((X-Z)-\{x\})=Z$. Zatem $f$ jest permutacją zbioru ${\mathcal {P}}(X)$. Co więcej łatwo zauważyć, że dla $Y$ o parzystej (nieparzystej) liczbie elementów $f(Y)$ ma nieparzystą (parzystą) liczbę elementów. To dowodzi, że dla parzystego $n$ podzbiorów $X$ o parzystej liczbie elementów jest tyle samo co podzbiorów $X$ o nieparzystej liczbie elementów.

Uogólniony współczynnik dwumianowy

Wniosek 5.8 pozwala na ustalenie wartość sumy całego wiersza w Trójkącie Pascala i wartość naprzemiennej sumy całego wiersza Trójkąta Pascala. W praktyce często pojawia się konieczność (naprzemiennego) sumowania tylko pewnego fragmentu takiego wiersza.Do tego pomocne mogłyby być sumy postaci:

${\begin{array}{lllc}\displaystyle \sum _{i=0}^{m}{n \choose i}&={n \choose 0}+{n \choose 1}+\ldots +{n \choose m}&\qquad (*)\\\displaystyle \sum _{i=0}^{m}(-1)^{i}{n \choose i}&={n \choose 0}-{n \choose 1}+\ldots +(-1)^{m}{n \choose m}&\qquad (**)\end{array}}$

dla $0\leqslant m<n$.

Niestety nie jest znana żadna zwarta postać $(*)$. Zaskakująca jest natomiast zwarta postać modyfikacji tej sumy polegającej na wymnożeniu każdego składnika przez jego odległość od środka trójkąta. Indukcyjny dowód tak powstałej zależności pozostawiamy jako ćwiczenie.

Obserwacja 5.9

Dla $m,n\geqslant 0$

$\displaystyle \sum _{i=0}^{m}{{\frac {n}{2}}-i}\cdot {n \choose i}={\frac {m+1}{2}}{n \choose m+1}.$

Natomiast naprzemienna częściowa suma $(**)$ wiersza Trójkąta Pascala ma postać zwartą. Wyprowadzenie takiej postaci odwołuje się do uogólnienia współczynnika dwumianowego na dowolne rzeczywiste indeksy górne, i dowolne całkowite indeksy dolne. Wykorzystuje to poznane już przy okazji rachunku róznicowego pojęcie dolnej silni $r^{\underline {k}}$.

Uogólniony współczynnik dwumianowy ${r \choose k}$ dla $r\in \mathbb {R}$ i $k\in \mathbb {Z}$ to:

${r \choose k}={\begin{cases}{\frac {r(r-1)\cdot \ldots \cdot (r-k+1)}{k(k-1)\cdot \ldots \cdot 1}}={\frac {r^{\underline {k}}}{k!}},&{\mbox{dla }}{k\geqslant 0},\\0,&{\mbox{dla }}{k<0}.\end{cases}}$

Zauważmy, że w istocie dla $r,k\in \mathbb {N}$ wartości ${r \choose k}$ pozostają niezmienione. Oczywiście, dla $r\in \mathbb {N}$, interpretacja ${r \choose k}$ jako $k$-elementowych liczby podzbiorów zbioru $r$-elementowego pozostaje w mocy. Nie jest natomiast znana sensowna kombinatoryczna interpretacja uogólnionego współczynnika dwumianowego dla pozostałych rzeczywistych wartosci $r$. Odnotujmy tylko, że ${r \choose k}$ jest wielomianem $k$-tego stopnia zmiennej $r$. Sporo własności współczynnika dwumianowego przenosi się na wersję uogólnioną. Poniższe zostawiamy bez dowodu jako ćwiczenie.

Obserwacja 5.10

Dla $r\in \mathbb {R} \Re$ i $k\in \mathbb {Z}$ mamy

• ${r \choose 0}=1$,

• ${r \choose 1}=r$,

• ${r \choose 2}={\frac {r(r-1)}{2}}$,

• ${-1 \choose k}=(-1)^{k+1}$, dla $k\geqslant 0$.

Przykład

Z uwagi na to, że w indeksie dolnym mogą występować jedynie liczby całkowite, nie ma sensu reguła symetrii ${r \choose k}={r \choose k-1}$. Ale nawet dla całkowitych wartości $r$ zawodzi:

${-1 \choose k}\neq {-1 \choose -1-k},\qquad {\mbox{dla dowolnych }}{k}.$

• jeśli $k<0$, to ${-1 \choose k}\neq {-1 \choose -1-k}=(-1)^{-1-k+1}$,

• jeśli $k\geqslant 0$, to ${-1 \choose k}=(-1)^{k+1}\neq 0={-1 \choose -1-k}$.

Zachowana jest natomiast reguła dodawania.

Obserwacja 5.11

Dla $r\in \mathbb {R} \Re$ i $k\in \mathbb {Z}$

${r \choose k}={r-1 \choose k}+{r-1 \choose k-1}.$

Dowód

Dla ujemnych wartości $k$ wszystkie współczynniki równe są $0$ i tożsamość trywialnie zachodzi. Niech teraz $r\in \mathbb {R} \Re$ i $k\geqslant 0$. Oczywiście różnica

${r \choose k}-{r-1 \choose k}-{r-1 \choose k-1}$

jest wielomianem co najwyżej $k$. Może więc, o ile nie jest wielomianem stale równym zero, mieć co najwyżej $k$ miejsc zerowych. Z drugiej strony wiemy już, że ta różnica zeruje się dla wszystkich liczb naturalnych $r$, więc musi być zawsze równa $0$.

Plik:4.9.svg

4.9.swf

Uogólniona reguła dodawania z Obserwacji 5.11 pozwala rozszerzyć Trójkąt Pascala na współczynniki o ujemnych wartościach górnego indeksu.

Kolejne wartości "ujemnej części" możemy wyliczać w następującej kolejności:

${-1 \choose 0},{-2 \choose 0},{-1 \choose 1},{-3 \choose 0},{-2 \choose 1},{-1 \choose 2},\ldots .$

Przyjrzyjmy się wartościom ${n \choose k}$ dla ustalonego $k$ i całkowitych wartości $n$. Zauważalny jest pewien rodzaj symetrii między tymi wartościami. W istocie zachodzi on dla wszystkich rzeczywistych wartości górnego indeksu.

Obserwacja 5.12 [reguła negacji górnego indeksu]

Dla $r\in \mathbb {R} \Re$, $k\in \mathbb {Z}$:

$(-1)^{k}{r \choose k}={k-r-1 \choose k}.$

Dowód

Policzymy wartość obu stron po uprzednim wymnożeniu przez wspólny mianownik $k!$:

${\begin{aligned}(-1)^{k}r^{\underline {k}}&=(-1)^{k}r(r-1)\cdot \ldots \cdot (r-k+1)\\&=(-r)(1-r)\cdot \ldots \cdot (k-1-r)\\&=(k-r-1)^{\underline {k}}.\end{aligned}}$

Znaną nam już z Obserwacji 5.5 regułę równoległego sumowania możemy uogólnić za pomocą argumentu podobnego do użytego w dowodzie Obserwacji 5.11.

Obserwacja 5.13

Dla $r\in \mathbb {R} \Re$, $k\in \mathbb {Z}$

$\displaystyle \sum _{i\leqslant k}{r+i \choose i}={r+k+1 \choose k}.$

Zauważmy, że rozważana suma jest tylko pozornie nieskończona, gdyż dla wszystkich ujemnych wartości $i$ odpowiednie składniki zerują się. W dalszych ciągu przyjmiemy będziemy również rozważać podobne sumy "nieskończone", ale przy założeniu, że tylko skończenie wiele składników jest niezerowych.

Wyposażeni w regułę negacji górnego indeksu wracamy teraz my do naprzemiennej, cześciowej sumy wierszy w Trójkącie Pascala, czyli do $(**)$.

Obserwacja 5.14

Dla $r\in \mathbb {R} \Re$, $m\in \mathbb {Z}$

$\displaystyle \sum _{i\leqslant m}(-1)^{i}{r \choose i}=(-1)^{m}{r-1 \choose m}.$

Dowód

${\begin{aligned}\sum _{i\leqslant m}(-1)^{i}{r \choose i}&=\sum _{i\leqslant m}{i-r-1 \choose i}\qquad {\text{z reguły negacji górnego indeksu}}\\&={-m+r \choose m}\qquad \qquad {\text{z Obserwacji 5.13}}\\&=(-1)^{m}{r-1 \choose m}.\qquad {\text{z reguły negacji górnego indeksu}}\end{aligned}}$

Przedstawimy teraz tożsamość, której później użyjemy do zliczenia pewnych, szczególnych permutacji. Zaczniemy od pomocniczej obserwacji.

Obserwacja 5.15 [przestawienie trójmianowe]

Dla $r\in \mathbb {R} \Re$, $i,j\in \mathbb {Z}$

${r \choose i}{i \choose j}={r \choose j}{r-j \choose i-j}.$

Dowód

Zauważmy, że dla $i<j$ obie strony równości się zerują. Także dla $i<0$ teza jest trywialna. Zatem możemy założyć, że $0\leqslant i<j$. Wtedy:

${\begin{aligned}{r \choose i}{i \choose j}&={\frac {r^{\underline {i}}}{i!}}\cdot {\frac {i^{\underline {j}}}{j!}}\\&={\frac {r(r-1\cdot \ldots \cdot (r-i+1))}{i!}}\cdot {\frac {i(i-1)\cdot \ldots \cdot (i-j+1)}{j!}}\\&={\frac {r(r-1)\cdot \ldots \cdot (r-j+1)}{j!}}\cdot {\frac {(r-j)(r-j-1)\cdot \ldots \cdot (r-i+1)}{(i-j)!}}\\&={r \choose j}{r-j \choose i-j}.\end{aligned}}$

Obserwacja 5.16 [reguła odwracania]

Dla funkcji $f,g:\mathbb {Z} \mathbb {R} \Re$

$\displaystyle f(n)=\sum _{i\in \mathbb {Z} }{n \choose i}(-1)^{i}g(i)$

wtedy i tylko wtedy, gdy

$\displaystyle g(n)=\sum _{i\in \mathbb {Z} }{n \choose i}(-1)^{i}f(i).$

Dowód

Z uwagi na symetrię założeń wystarczy udowodnić tylko jedne implikację. Zakładamy zatem, że $\displaystyle f(n)=\sum _{i\in \mathbb {Z} }{n \choose i}(-1)^{i}g(i)$ by dostać:

${\begin{aligned}\sum _{i}{n \choose i}(-1)^{i}f(i)&=\sum _{i\in \mathbb {Z} }{n \choose i}(-1)^{i}\sum _{j\in \mathbb {Z} }{i \choose j}(-1)^{j}g(j)\\&=\sum _{j\in \mathbb {Z} }g(j)\sum _{i\in \mathbb {Z} \mathbb {Z} }{n \choose i}{i \choose j}(-1)^{i+j}\\&=\sum _{j\in \mathbb {Z} }g(j)\sum _{i\in \mathbb {Z} \mathbb {Z} }{n \choose j}{n-j \choose i-j}(-1)^{i+j}\\&=\sum _{j\in \mathbb {Z} }g(j){n \choose j}\sum _{i\in \mathbb {Z} }{n-j \choose i-j}(-1)^{i+j}\\&=\sum _{j\in \mathbb {Z} }g(j){n \choose j}\sum _{i\in \mathbb {Z} }{n-j \choose i}(-1)^{i},\end{aligned}}$

gdzie druga równość wynika ze zmiana kolejności sumowania, trzecia z przestawienia trójmianowego, a ostatnia przez podstawienie $i:=i+j$.

Z Wniosku 5.8 wiemy, że suma $\displaystyle \sum _{i\in \mathbb {Z} }{n-j \choose i}(-1)^{i}$ jest niezerowa (i wynosi $1$) tylko dla $j=n$. Zatem kontynuując:

${\begin{aligned}&=\sum _{j\in \mathbb {Z} }g(j){n \choose j}\sum _{i\in \mathbb {Z} }{n-j \choose i}(-1)^{i}\\&=g(n){n \choose n}=g(n).\end{aligned}}$

Permutacje bez punktów stałych

Nieporządek na zbiorze $X$ to permutacja $\alpha :X\to X$ taka, że $\alpha (x)\neq x$ dla dowolnego $x\in X$, czyli permutacja "bez punktów stałych".

Podsilnia liczby $n$, w skrócie $!n$, to liczba nieporządków zbioru $n$-elementowego. Przyjmujemy, że $!0=1$, jako ze jedyna permutacja zbioru pustego - funkcja pusta - w oczywisty sposób nie ma punktów stałych.

Przykład

Zbiór $\mathbb {Z} _{4}=\{0,1,2,3\}$ ma $4!=24$ permutacje, ale tylko $9$ z nich to nieporządki. Oto ich lista:

${\begin{array}{cccccccccccccc}0&1&2&3&\qquad &0&1&2&3&\qquad &0&1&2&3\\\downarrow &\downarrow &\downarrow &\downarrow &\qquad &\downarrow &\downarrow &\downarrow &\downarrow &\qquad &\downarrow &\downarrow &\downarrow &\downarrow \\1&0&3&2&\qquad &1&2&3&0&\qquad &1&3&0&2\\\\0&1&2&3&\qquad &0&1&2&3&\qquad &0&1&2&3\\\downarrow &\downarrow &\downarrow &\downarrow &\qquad &\downarrow &\downarrow &\downarrow &\downarrow &\qquad &\downarrow &\downarrow &\downarrow &\downarrow \\2&0&3&1&\qquad &2&3&0&1&\qquad &2&3&1&0\\\\0&1&2&3&\qquad &0&1&2&3&\qquad &0&1&2&3\\\downarrow &\downarrow &\downarrow &\downarrow &\qquad &\downarrow &\downarrow &\downarrow &\downarrow &\qquad &\downarrow &\downarrow &\downarrow &\downarrow \\3&0&1&2&\qquad &3&2&0&1&\qquad &3&2&1&0\end{array}}$

Obserwacja 5.17

$\displaystyle !n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}$.

Dowód

Zauważmy najpierw, że liczba permutacji $\alpha$ zbioru $n$-elementowego takich, że $\alpha (x)\neq x$ dla dokładnie $i$ elementów $x\in X$, wynosi ${n \choose i}!i$. Stąd:

$\displaystyle n!=\sum _{i=0}^{n}{n \choose i}!i=\sum _{i=0}^{n}(-1)^{i}{n \choose i}(-1)^{i}(!i).$

Stosując teraz regułę odwracania, dostajemy:

${\begin{aligned}!n&=\sum _{i=0}^{n}(-1)^{n-i}{n \choose i}i!\\&=\sum _{i=0}^{n}(-1)^{n-i}{\frac {n!}{(n-i)!}}\\&=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}.\end{aligned}}$

Współczynniki multimianowe

Współczynniki dwumianowe pojawiały się przy rozwinięciu dwumianu $(x+y)^{n}$. Odpowiadały one wyborom dwuwartościowym. Podobnie rozważając trójmian $(x+y+z)^{n}$, czy ogólnie $(x_{1}+\ldots +x_{r})^{n}$, pojawią się współczynniki odpowiadające wyborom odpowiedni trój- i $r$-wartościowym. Wybieranie podzbioru $k$-elementowego ze zbioru $n$-elementowego to podział zbioru na dwie części o odpowiednio $k$ i $n-k$ elementach. Naturalnym uogólnieniem, będzie podział zbioru $n$-elementowego na $r$ części o odpowiednio $k_{1},k_{2},\ldots ,k_{r}$ elementach, przy czym oczywiście $k_{1}+\ldots k_{r}=n$.

Współczynnik multimianowy ${n \choose k_{1},k_{2}\ldots ,k_{r}}$, dla $n\in \mathbb {Z}$, $r\geqslant 2$ oraz całkowitych $k_{1},\ldots ,k_{r}$ takich, że $k_{1}+\ldots k_{r}=n$, to liczba sposobów umieszczenia $n$ obiektów w $r$ pudełkach z odpowiednio $k_{1}$ obiektami w pierwszym pudełku, $k_{2}$ w drugim, itd., oraz $k_{r}$ w $r$-tym. Jeśli którakolwiek z liczb $k_{i}$ jest ujemna to współczynnik jest równy $0$. Zauważmy, że z uwagi na symetrię dolnych indeksów, ich kolejność nie jest istotna. Oczywiście ${n \choose k}$ to w nowej notacji ${n \choose k,n-k}$.

Następna obserwacja wynika wprost z definicji współczynników multimianowych.

Obserwacja 5.18

Dla $n\in \mathbb {Z}$, $k,l,k_{1},\ldots ,k_{r}\in \mathbb {Z}$ takich, że $k_{1}+\ldots k_{r}=n=k+l$ zachodzi:

• ${n \choose n,0,\ldots ,0}=1$,

• ${n \choose 1,1,\ldots ,1}=1$,

• ${n \choose 0,k_{1},\ldots ,k_{r}}={n \choose k_{1},\ldots ,k_{r}}$,

• ${n \choose l,l,0,\ldots ,0}={n \choose k}={n \choose l}$,

• ${n \choose k_{1},\ldots ,k_{r}}={n \choose k_{\sigma (1)},\ldots ,k_{\sigma (r)}}$, dla dowolnej permutacji $\sigma$ zbioru $\{1,2,\ldots ,r\}$.

Następna obserwacja wymaga krótkiego uzasadnienia.

Obserwacja 5.19

Dla $n,k_{1},\ldots ,k_{r}\geqslant 0$ takich, że $k_{1}+\ldots +k_{r}=n$

${n \choose k_{1},\ldots ,k_{r}}={n \choose k_{1}}{n-k_{1} \choose k_{2}}{n-(k_{1}+k_{2}) \choose k_{3}}\cdot \ldots \cdot {n-(k_{1}+\ldots +k_{r-1}) \choose k_{r}}.$

Dowód

Rozmieszczenie $n$-obiektów w $r$ pudełkach po $k_{i}$ w każdym, polega na:

• wyborze $k_{1}$ obiektów spośród wszystkich $n$ i umieszczeniu ich w pierwszym pudełku - możemy to uczynić na ${n \choose k_{1}}$ sposobów,

• wyborze $k_{2}$ obiektów spośród pozostałych $n-k_{1}$ i umieszczeniu ich w drugim pudełku - możemy to uczynić na ${n-k_{1} \choose k_{2}}$ sposobów,

• wyborze $k_{3}$ obiektów spośród pozostałych $n-(k_{1}+k_{2})$

i umieszczeniu ich w trzecim pudełku - możemy to uczynić na ${n-(k_{1}+k_{2}) \choose k_{3}}$ sposobów,

• ...

• wyborze $k_{r}$ obiektów spośród pozostałych $n-(k_{1}+\ldots +k_{r-1})=k_{r}$ i umieszczeniu ich w ostatnim pudełku - możemy to uczynić na ${n-(k_{1}+\ldots +k_{r-1}) \choose k_{r}}={k_{r} \choose k_{r}}=1$ sposobów.

Zatem wszystkich możliwych rozmieszczeń zgodnie z wymogami z definicji

współczynnika multimianowego jest dokładnie ${n \choose k_{1}}{n-k_{1} \choose k_{2}}{n-(k_{1}+k_{2}) \choose k_{3}}\cdot \ldots \cdot {n-(k_{1}+\ldots +k_{r-1}) \choose k_{r}}$.

Wniosek 5.20

Dla $n,k_{1},\ldots ,k_{r}\geqslant 0$ takich, że $k_{1}+\ldots +k_{r}=n$

${n \choose k_{1},\ldots ,k_{r}}={\frac {n!}{k_{1}!\cdot \ldots \cdot k_{r}!}}.$

Dowód

${\begin{aligned}{n \choose k_{1},\ldots ,k_{r}}&={n \choose k_{1}}{n-k_{1} \choose k_{2}}{n-(k_{1}+k_{2}) \choose k_{3}}\cdot \ldots \cdot {n-(k_{1}+\ldots +k_{r-1}) \choose k_{r}}\\&={\frac {n!}{(n-k_{1})!k_{1}!}}\cdot {\frac {(n-k_{1})!}{(n-(k_{1}+k_{2}))!k_{2}!}}\cdot \ldots \cdot {\frac {(n-(k_{1}+\ldots +k_{r-1}))!}{(n-(k_{1}+\ldots +k_{r}))!k_{r}!}}\\&={\frac {n!}{k_{1}!\cdot \ldots \cdot k_{r}!\cdot (n-(k_{1}+\ldots +k_{r}))!}}\\&={\frac {n!}{k_{1}!\cdot \ldots \cdot k_{r}!}}.\end{aligned}}$

Przykład

Ile liczb możemy ułożyć zapisując w dowolnej kolejności $11$ cyfr: $1,1,3,4,5,5,5,6,7,7,9$?

Zauważmy, że każda taka liczba powstaje przez wybór dwu pozycji dla cyfry $1$, jednej dla cyfry $3$, jednej dla cyfry $4$, trzech dla cyfry $5$, jednej dla cyfry $6$, dwu dla cyfry $7$ i wreszcie jednej pozycji dla cyfry $9$. Zatem $11$ pozycji to nasze obiekty, które rozmieszczamy w siedmiu pudełkach etykietowanych cyframi: $1,3,4,5,6,7,9$. Zatem z definicji współczynnika multimianowego mamy:

${11 \choose 2,1,1,3,1,2,1}={\frac {11!}{2!\cdot 3!\cdot 2!}}=1663200.$

Przykład

Rozważmy raz jeszcze podróż w mieście o ulicach na planie siatki. Tym razem jednak... $3$-wymiarową wersję. Mamy więc do dyspozycji trójwymiarową, prostopadłościenną kratownicę $a\times b\times c$. Na ile sposobów można połączyć przeciwległe wierzchołki prostopadłoscianu najkrótszą możliwą łamaną Zauważmy, że każda najkrótsza możliwa łamana składa się z dokładnie $a+b+c$ odcinków jednostkowych. Przy czym dokładnie $a$ z nich jest poziomych, $b$ pionowych i $c$ idzie w głąb. Zatem najkrótszych łamanych jest tyle co rozmieszczeń $a+b+c$ odcinków (obiekty) w $3$ pudełkach: "poziomy", "pionowy", "w głąb" tak, by w było ich odpowiednio $a,b$ i $c$. Z definicji współczynnika multimianowego mamy zatem:

${a+b+c \choose a,b,c}={\frac {(a+b+c)!}{a!b!c!}},$

łamanych.

Kratka z rysunku o wymiarach $3\times 4\times 2$ ma zatem: ${9 \choose 3,4,2}={\frac {9!}{3!\cdot 4!\cdot 2!}}=420$ interesujących nas łamanych.

Współczynniki multimianowe także zachowują pewną regułę dodawania.

Obserwacja 5.21

Dla $n>0$, całkowitych $k_{1},\ldots ,k_{r}$ takich, że $k_{1}+\ldots +k_{r}=n$

${n \choose k_{1}}={n-1 \choose k_{1}-1,k_{2},\ldots ,k_{r}}+{n-1 \choose k_{1},k_{2}-1,\ldots ,k_{r}}+\ldots +{n-1 \choose k_{1},k_{2},\ldots ,k_{r}-1}.$

Dowód

Ponieważ $n>0$, możemy wybrać i ustalić ulubiony obiekt $x$. Możemy go umieścić w jednym z $r$ pudełek. Jeśli jednak umieścimy go w pierwszym, to pozostałe $n-1$ obiektów musimy rozłożyć do $r$ pudeł zgodnie z warunkami wyjściowymi, ale do pierwszej szuflady mamy włożyć już $1$ obiekt mniej ($k_{1}-1$ a nie $k_{1}$). Rozłożenia tego możemy dokonać na ${n \choose k_{1}-1,k_{2},\ldots ,k_{r}}$. Analogicznie gdy $x$ umieścimy w drugim pudle, to pozostałe przedmioty rozkładamy w pudłach odpowiednio po $k_{1},k_{2}-1,k_{3},\ldots ,k_{r}$. Po przesumowaniu po numerach pudła, w którym jest $x$ dostajemy nasz wzór.

Jako ćwiczenie pozostawiamy dowód następującego uogólnienia wzoru dwumiennego:

Obserwacja 5.22

$\displaystyle (x_{1}+\ldots +x_{r})^{n}=\sum _{k_{1}+\ldots +k_{r}=n}{n \choose k_{1},\ldots ,k_{r}}x_{1}^{k_{1}}x_{2}^{k_{2}}\ldots x_{r}^{k_{r}}.$