Matematyka dyskretna 1/Wykład 5: Współczynniki dwumianowe: Różnice pomiędzy wersjami

Wersja z 10:04, 22 sie 2006

Zliczanie podzbiorów raz jeszcze

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 $𝒫_{k} (X)$ .

Współczynnik dwumianowy $(\binom{n}{k})$ to liczba $k$ -elementowych podzbiorów zbioru $n$ -elementowego, tzn. Parser nie mógł rozpoznać (nieznana funkcja „\abs”): {\displaystyle {n\choose k} = \abs{|{\mathcal P}_k(\mathbb{Z}\integer_n)|}} . Wyrażenie $(\binom{n}{k})$ czytamy $n$ po $k$ .

foto,notka Ettinghausen

Prawdopodobnie jako pierwszy tej notacji użył Albert von Ettinghausen 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ć $(\binom{4}{2})$ wypiszmy wszystkie $2$ -elementowe podzbiory $4$ -elementowego zbioru Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle \mathbb{Z}\integer_4=\set\{0,1,2,3\}} . Sa to Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{0,1\}} , Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{0,2\}} , Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{0,3\}} , Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{1,2\}} , Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{1,3\}} , Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{2,3\}} ,

skąd

(\binom{4}{2}) = 6

.

Bezpośrednio z definicji liczb $(\binom{n}{k})$ dostajemy:

Obserwacja 5.1

Dla Parser nie mógł rozpoznać (nieznana funkcja „\natur”): {\displaystyle n,k \in \natur \mathbb{R}} zachodzi:

$(\binom{n}{0}) = (\binom{n}{n}) = 1$ ,

$(\binom{n}{k}) = 0$ , dla $k > n$ ,

$(\binom{n}{1}) = n$ , dla $n > 0$ ,

$(\binom{n}{k}) = (\binom{n}{n - k})$ , dla $n ⩾ k ⩾ 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 Parser nie mógł rozpoznać (nieznana funkcja „\abs”): {\displaystyle \abs|{X}|=n\geqslant k\geqslant 0} . Wtedy funkcja

𝒫_{k} (X) ∋ A \mapsto X ∖ A \in 𝒫_{n - k} (X)

jest bijekcją. A zatem istotnie $(\binom{n}{k}) = (\binom{n}{n - k})$ .

Nasza następna obserwacja stanowi fundament dla rekurencyjnej procedury obliczania współczynników dwumianowych.

Obserwacja 5.2

Dla $0 < k ⩽ n$ mamy:

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) .

Dowód

Podobnie jak przy budowaniu zależności rekurencyjnej przy zliczaniu wszystkich podzbiorów zbioru $n$ -elementowego załóżmy, że Parser nie mógł rozpoznać (nieznana funkcja „\abs”): {\displaystyle \abs|{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 $(\binom{n - 1}{k})$ .

Każdy zaś podzbiór pierwszego typu, czyli $A \in 𝒫_{k} (Z)$ takie, że $a \in A$ jest jednoznacznie wyznaczony przez swoje pozostałe $k - 1$ elementów, czyli Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle A=A'\cup \set\{a\}} dla pewnego $A^{'} \in 𝒫_{k - 1} (Z^{'})$ . A zatem

Parser nie mógł rozpoznać (nieznana funkcja „\abs”): {\displaystyle {n \choose k} = \abs{|{\mathcal P}_k(Z)|} = \abs{|{\mathcal P}_k(Z')|} + \abs{|{\mathcal P}_{k-1}(Z')|} = {n-1\choose k}+{n-1\choose k-1}. }

Trójkąt Pascala foto,notka Pascal (nazwany na cześć Blaise'a Pascala, który napisał znakomitą rozprawę o współczynnikach dwumianowych) bazuje na własności $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ i ustawia liczby w następujący sposób:

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

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

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

Są to kolejno $(\binom{n}{0}), (\binom{n}{1}), (\binom{n}{2}), \dots, (\binom{n}{n - 1}), (\binom{n}{n})$


					$(\binom{0}{0})$
				$(\binom{1}{0})$		$(\binom{1}{1})$
			$(\binom{2}{0})$		$(\binom{2}{1})$		$(\binom{2}{2})$
		$(\binom{3}{0})$		$(\binom{3}{1})$		$(\binom{3}{2})$		$(\binom{3}{3})$
	$(\binom{4}{0})$		$(\binom{4}{1})$		$(\binom{4}{2})$		$(\binom{4}{3})$		$(\binom{4}{4})$
$(\binom{5}{0})$		$(\binom{5}{1})$		$(\binom{5}{2})$		$(\binom{5}{3})$		$(\binom{5}{4})$		$(\binom{5}{5})$
	...		...		...		...		...

Przesunięcie w wierszach, pozwala wyliczyć $(\binom{n}{k})$ jako sumę $(\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ dwu liczb stojących bezpośrednio nad $(\binom{n}{k})$ :

Uzupelnij tytul
					1
				1		1
			1		2		1
		1		3		3		1
	1		4		6		4		1
1		5		10		10		5		1
	...		...		...		...		...

{{przyklad||| Napisz program drukujący trójkąt Pascala, ale z liczbami $(\binom{n}{k})$ modulo $2$ , tzn. w miejsce $(\binom{n}{k})$ wstaw jedynie resztę $0$ lub $1$ z dzielenia liczby $(\binom{n}{k})$ przez $2$ . Zaobserwuj na wydruku powstały fraktal. Wyjaśnij dlaczego tak się dzieje.

Rys. 4.1 Szkic na kartce.

W trójkącie Pascala współczynniki o tym samym górnym indeksie, np.

Parser nie mógł rozpoznać (nieznana funkcja „\krot”): {\displaystyle \left \langle \krot{4\choose0},{4\choose1},{4\choose2},{4\choose3},{4\choose4}\right \rangle =\left \langle \krot{1,4,6,4,1}\right \rangle }

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

Parser nie mógł rozpoznać (nieznana funkcja „\krot”): {\displaystyle \left \langle \krot{5\choose5},{6\choose5},{7\choose5},{8\choose5},\ldots}\right \rangle =\left \langle \krot{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 ⩽ k ⩽ n$

(\binom{n}{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ę Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle \mathbb{Z}\integer_k \map 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 \dots \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 $(\binom{0}{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 $(\binom{n + 1}{k})$ dla Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle k\in\set\{0,\ldots,n+1\}} . Jeśli $k = 0$ to $(\binom{n + 1}{k}) = 1 = \frac{n!}{(n - 0)! 0!}$ . Załóżmy więc, że $k > 0$ . Wtedy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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!}. \endaligned}

Przykład

(\binom{15}{3}) = \frac{15!}{(15 - 3)! 3!} = \frac{13 \cdot 14 \cdot 15}{2 \cdot 3} = 13 \cdot 7 \cdot 5 = 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.

4.2 Szkic na kartce.

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

4.3 Szkic na kartce.

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 $(\binom{9}{3}) = (\binom{9}{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

(\binom{m + n}{m}) = (\binom{m + n}{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 \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:

4.4 Szkic na kartce.

4.5 Szkic na kartce.

Zatem istnieje $(\binom{7 + 4}{4}) = 330$ rozwiązań naszego równania.

W ogólności, równanie

x_{0} + x_{1} + \dots + 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

(\binom{n + k - 1}{n}) = (\binom{n + k - 1}{k - 1})

.

Przykład

Ile rozwiązań ma równanie

x_{0} + \dots + 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} ⩾ 1$ , można otrzymać z rozwiązania w liczbach naturalnych równania

y_{0} + \dots + y_{k - 1} = n - k,

poprzez podstawienie $x_{i} = y_{i} + 1$ . Na podstawie poprzedniego przykładu poszukiwanych rozwiązań jest zatem $(\binom{n - 1}{k - 1})$ . Rozważmy $n$ obiektów (np. punktów) ustawionych w ciągu jeden przy drugim.

6.1 Szkic na kartce.

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:

6.2 Szkic na kartce.

Na odwrót każde rozwiązanie $x_{0}, x_{1}, \dots, 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

(\binom{n - 1}{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?

Rys. 4.11 Szkic na kartce.

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 $(\binom{n + 1}{2})$ sposobów i pionowe linie także na $(\binom{n + 1}{2})$ sposobów. Zatem prostokąt w kratce $n \times n$ możemy narysować na dokładnie

{(\binom{n + 1}{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 Parser nie mógł rozpoznać (nieznana funkcja „\natur”): {\displaystyle n,k\in\natur\mathbb{N}} mamy

\sum_{i = 0}^{n} (\binom{i}{k}) = (\binom{n + 1}{k + 1}) .

4.6 Szkic na kartce.

Dowód

Ustalmy $(n + 1)$ -elementowy zbiór Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle X=\set\{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 ⩾ k$ , gdyż Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle X=\set\{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 Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{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 Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{x_0,\ldots,x_{i-1}\}} . Wyboru tych elementów można dokonać na $(\binom{i}{k})$ sposobów. Zatem podzbiorów zbioru $X$ , w których $x_{i}$ jest elementem o największym indeksie jest dokładnie $(\binom{i}{k})$ . Sumując po wszystkich możliwych $i$ , czyli Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle i\in\set\{k,\ldots,n\}} otrzymujemy:

\sum_{i = 0}^{n} (\binom{i}{k}) = \sum_{i = k}^{n} (\binom{i}{k}) = (\binom{n + 1}{k + 1}) .

Podobnie możemy sumować liczby położone na linii "prostopadłej" do przekątnych Trójkąta Pascala, czyli liczby postaci $(\binom{n + i}{i})$ .

Obserwacja 5.5 [reguła sumowania równoległego]

Dla Parser nie mógł rozpoznać (nieznana funkcja „\natur”): {\displaystyle n,k\in\natur\mathbb{N}} mamy:

\sum_{i = 0}^{k} (\binom{n + i}{i}) = (\binom{n + k + 1}{k}) .

4.7 Szkic na kartce.

Dowód

Tożsamość tę udowodnimy wykorzystując dwukrotnie {regułę symetrii} oraz {regułę sumowania po górnym indeksie}:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}. \endaligned}

Obserwacja 5.6 [tożsamość Cauchy'ego, splot Vandermonde'a]

Dla liczb naturalnych $m, n, k$ mamy:

\sum_{i = 0}^{k} (\binom{m}{i}) (\binom{n}{k - i}) = (\binom{m + n}{k}) .

Dowód

Policzymy liczbę wszystkich wyborów $k$ osób z grona $m$ mężczyzn i $n$ kobiet, czyli liczbę $(\binom{m + n}{k})$ na jeszcze jeden sposób. Wybierając $k$ osób wybieramy najpierw $i$ mężczyzn na $(\binom{m}{i})$ sposobów, a potem $k - i$ kobiet na $(\binom{n}{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 7 [Twierdzenie o Dwumianie]

Dla $x, y \in ℝ$ i $n \in ℕ$

(x + y)^{n} = \sum_{i = 0}^{n} (\binom{n}{i}) x^{i} y^{n - i} .

Dowód [Uzupelnij]

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

\underset{n r a z y}{\underset{⏟}{(x + y) \cdot \dots \cdot (x + y)}} .

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 \dots \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 $(\binom{n}{k})$ -krotnie.

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

Przykład [Uzupelnij]

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned(a+b)^2&=&a^2+2ab+b^2,\\ (a+b)^3&=&a^3+3a^2b+3ab^2+b^3,\\ (a+b)^4&=&a^4+4a^3b+6a^2b^2+4ab^3+b^4. \endaligned}

Wniosek 8

Dla dowolnego

n ⩾ 0

$(1 + x)^{n} = \sum_{i = 0}^{n} (\binom{n}{i}) x^{i}$ ,

$(\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = 2^{n}$ ,

$(\binom{n}{0}) - (\binom{n}{1}) + \dots + (- 1)^{n} (\binom{n}{n}) = 0^{n}$ .

{ (Uwaga: $(\binom{0}{0}) = 1 = 0^{0}$ )}

{4.8 Szkic na kartce.}

Dowód [Uzupelnij]

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, \dots$ -elementowe -- jest ich $(\binom{n}{0}), (\binom{n}{1}), (\binom{n}{2}), \dots$ .

Nieco dłuższy jest argument kombinatoryczny dla naprzemiennej sumy $(\binom{n}{0}) - (\binom{n}{1}) + \dots + (- 1)^{n} (\binom{n}{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ę Parser nie mógł rozpoznać (nieznana funkcja „\map”): {\displaystyle f:\mathcal{P}(X)\map\mathcal{P}(X)} , kładąc

Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle f(Y)= \begin{cases} (X - Y)-\set\{x\} \mbox{, jeśli } {x}\not\in {Y}\subseteq {X},}\\ (X - Y)\cup\set\{x\} \mbox{, jeśli } {x}\in {Y}\subseteq {X}. \end{cases}}

Zauważmy, że $f$ jest permutacją $𝒫 (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

Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle f(Y_1)=(X-Y_1)-\set\{x\}=X-Y_1\neq X-Y_2=(X-Y_2)-\set\{x\}=f(Y_2), }

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

Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle f(Y_1)=(X-Y_1)\cup\set\{x\}\neq(X-Y_1)\cup\set\{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 Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle f((X-Z)\cup\set\{x\})=Z} , jeśli zaś $x \notin Z$ to Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle f((X-Z)-\set\{x\})=Z} . Zatem $f$ jest permutacją zbioru $𝒫 (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 {[##wniosek - suma i naprzemienna suma wiersza|Uzupelnic wniosek - suma i naprzemienna suma wiersza|]} 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}{lclc} \sum_{i = 0}^{m} (\binom{n}{i}) & = & (\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{m}) & (*) \\ \sum_{i = 0}^{m} (- 1)^{i} (\binom{n}{i}) & = & (\binom{n}{0}) - (\binom{n}{1}) + \dots + (- 1)^{m} (\binom{n}{m}) & (* *) \end{array}

dla $0 ⩽ 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 9

Dla

m, n ⩾ 0

Parser nie mógł rozpoznać (nieznana funkcja „\brackets”): {\displaystyle \sum_{i=0}^m\brackets{\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} $(\binom{r}{k})$ dla $r \in ℝ$ i $k \in ℤ$ to:

(\binom{r}{k}) = {\begin{cases} \frac{r (r - 1) \cdot \dots \cdot (r - k + 1)}{k (k - 1) \cdot \dots \cdot 1} = \frac{r^{\underline{k}}}{k!}, & dla k ⩾ 0, \\ 0, & dla k < 0 . \end{cases}

Zauważmy, że w istocie dla Parser nie mógł rozpoznać (nieznana funkcja „\natur”): {\displaystyle r,k\in\mathbb{N}\natur} wartości $(\binom{r}{k})$ pozostają niezmienione. Oczywiście, dla Parser nie mógł rozpoznać (nieznana funkcja „\natur”): {\displaystyle r\in\mathbb{N}\natur} , interpretacja $(\binom{r}{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 $(\binom{r}{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 10

Dla

r \in ℝ ℜ

i Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle k\in\mathbb{Z}\integer} mamy

$(\binom{r}{0}) = 1$ ,

$(\binom{r}{1}) = r$ ,

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

$(\binom{- 1}{k}) = (- 1)^{k + 1}$ , dla $k ⩾ 0$ .

Przykład [Uzupelnij]

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

(\binom{- 1}{k}) \neq (\binom{- 1}{- 1 - k}), dla dowolnych k .

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

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

Zachowana jest natomiast {reguła dodawania}.

Obserwacja 11

Dla

r \in ℝ ℜ

i Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle k\in\mathbb{Z}\integer}

(\binom{r}{k}) = (\binom{r - 1}{k}) + (\binom{r - 1}{k - 1}) .

Dowód [Uzupelnij]

Dla ujemnych wartości $k$ wszystkie współczynniki równe są $0$ i tożsamość trywialnie zachodzi. Niech teraz $r \in ℝ ℜ$ i $k ⩾ 0$ . Oczywiście różnica

(\binom{r}{k}) - (\binom{r - 1}{k}) - (\binom{r - 1}{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$ .

Uogólniona reguła dodawania z Obserwacji {[##obserwacja - uogolniona regula dodawania|Uzupelnic obserwacja - uogolniona regula dodawania|]} pozwala rozszerzyć Trójkąt Pascala na współczynniki o ujemnych wartościach górnego indeksu.

{Rys. 4.9 Szkic na kartce.}

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

(\binom{- 1}{0}), (\binom{- 2}{0}), (\binom{- 1}{1}), (\binom{- 3}{0}), (\binom{- 2}{1}), (\binom{- 1}{2}), \dots .

Przyjrzyjmy się wartościom $(\binom{n}{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 12 [reguła negacji górnego indeksu]

Dla $r \in ℝ ℜ$ , Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle k\in\mathbb{Z}\integer} :

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

Dowód [Uzupelnij]

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}}. \endaligned}

Znaną nam już z Obserwacji {[##obserwacja - sumowanie rownolegle|Uzupelnic obserwacja - sumowanie rownolegle|]} regułę równoległego sumowania możemy uogólnić za pomocą argumentu podobnego do użytego w dowodzie Obserwacji {[##obserwacja - uogolniona regula dodawania|Uzupelnic obserwacja - uogolniona regula dodawania|]}.

Obserwacja 13

Dla

r \in ℝ ℜ

, Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle k\in\mathbb{Z}\integer}

\sum_{i ⩽ k} (\binom{r + i}{i}) = (\binom{r + k + 1}{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 14

Dla

r \in ℝ ℜ

, Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle m\in\mathbb{Z}\integer}

\sum_{i ⩽ m} (- 1)^{i} (\binom{r}{i}) = (- 1)^{m} (\binom{r - 1}{m}) .

Dowód [Uzupelnij]

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\sum_{i\leqslant m}(-1)^i{r\choose i} &=&\sum_{i\leqslant m}{i-r-1\choose i} \qquad\textrm{z reguły negacji górnego indeksu}\\ &=&{-m+r\choose m} \qquad\qquad\textrm{z Obserwacji [##Uzupelnic obserwacja - uogolnione sumowanie rownolegle]}\\ &=&(-1)^m{r-1\choose m}. \qquad\textrm{z reguły negacji górnego indeksu} \endaligned}

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

Obserwacja 15 [przestawienie trójmianowe]

Dla $r \in ℝ ℜ$ , Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle i,j\in\mathbb{Z}\integer}

(\binom{r}{i}) (\binom{i}{j}) = (\binom{r}{j}) (\binom{r - j}{i - j}) .

Dowód [Uzupelnij]

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 ⩽ i < j$ . Wtedy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}. \endaligned}

Obserwacja 16 [reguła odwracania]

Dla funkcji Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle f,g:\mathbb{Z}\integer\map\mathbb{R}\real}

Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle f(n)=\sum_{i\in\mathbb{Z}\integer}{n\choose i}(-1)^ig(i) }

wtedy i tylko wtedy, gdy

Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle g(n)=\sum_{i\in\mathbb{Z}\integer}{n\choose i}(-1)^if(i). }

Dowód [Uzupelnij]

Uzupelnic wniosek - suma i naprzemienna suma wiersza

Permutacje bez punktów stałych

{Nieporządek} na zbiorze $X$ to permutacja Parser nie mógł rozpoznać (nieznana funkcja „\map”): {\displaystyle \alpha:X\map X} taka, że $α (x) \neq x$ dla dowolnego $x \in X$ , czyli permutacja "bez punktów stałych".

{Podsilnia} liczby $n$ , w skrócie Parser nie mógł rozpoznać (nieznana funkcja „\fPodsilnia”): {\displaystyle \fPodsilnia{n}} , to liczba nieporządków zbioru $n$ -elementowego. Przyjmujemy, że Parser nie mógł rozpoznać (nieznana funkcja „\fPodsilnia”): {\displaystyle \fPodsilnia{0}=1} , jako ze jedyna permutacja zbioru pustego -- funkcja pusta -- w oczywisty sposób nie ma punktów stałych.

Przykład [Uzupelnij]

Zbiór Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle \mathbb{Z}\integer_4=\set\{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 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 \\ ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ \\ 1 & 0 & 3 & 2 & 1 & 2 & 3 & 0 & 1 & 3 & 0 & 2 \\ 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 \\ ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ \\ 2 & 0 & 3 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 1 & 0 \\ 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 \\ ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ \\ 3 & 0 & 1 & 2 & 3 & 2 & 0 & 1 & 3 & 2 & 1 & 0 \end{array}

Obserwacja 17

Parser nie mógł rozpoznać (nieznana funkcja „\fPodsilnia”): {\displaystyle \fPodsilnia{n} = n!\sum_{i=0}^n\frac{(-1)^i}{i!}} .

Dowód [Uzupelnij]

Zauważmy najpierw, że liczba permutacji $α$ zbioru $n$ -elementowego takich, że $α (x) \neq x$ dla dokładnie $i$ elementów $x \in X$ wynosi Parser nie mógł rozpoznać (nieznana funkcja „\fPodsilnia”): {\displaystyle {n\choose i}\fPodsilnia{i}} . Stąd:

Parser nie mógł rozpoznać (nieznana funkcja „\fPodsilnia”): {\displaystyle n!= \sum_{i=0}^n {n\choose i}\fPodsilnia{i} =\sum_{i=0}^n (-1)^i{n\choose i}(-1)^i\fPodsilnia{i}. }

Aplikując teraz regułę odwracania dostajemy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fPodsilnia{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!}. \endaligned}

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} + \dots + 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}, \dots, k_{r}$ elementach, przy czym oczywiście $k_{1} + \dots k_{r} = n$ .

{Współczynnik multimianowy} $(\binom{n}{k_{1}, k_{2} \dots, k_{r}})$ , dla Parser nie mógł rozpoznać (nieznana funkcja „\natur”): {\displaystyle n\in\mathbb{Z}\natur} , $r ⩾ 2$ oraz całkowitych $k_{1}, \dots, k_{r}$ takich, że $k_{1} + \dots 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 $(\binom{n}{k})$ to w nowej notacji $(\binom{n}{k, n - k})$ .

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

Obserwacja 18

Dla Parser nie mógł rozpoznać (nieznana funkcja „\natur”): {\displaystyle n\in\mathbb{Z}\natur} , Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle k,l,k_1,\ldots,k_r\in\mathbb{Z}\integer} takich, że

k_{1} + \dots k_{r} = n = k + l

zachodzi:

$(\binom{n}{n, 0, \dots, 0}) = 1$ ,

$(\binom{n}{1, 1, \dots, 1}) = 1$ ,

$(\binom{n}{0, k_{1}, \dots, k_{r}}) = (\binom{n}{k_{1}, \dots, k_{r}})$ ,

$(\binom{n}{l, l, 0, \dots, 0}) = (\binom{n}{k}) = (\binom{n}{l})$ ,

$(\binom{n}{k_{1}, \dots, k_{r}}) = (\binom{n}{k_{σ (1)}, \dots, k_{σ (r)}})$ ,

dla dowolnej permutacji $σ$ zbioru Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{1,2,\ldots,r\}} .

Następna obserwacja wymaga krótkiego uzasadnienia.

Obserwacja 19

Dla

n, k_{1}, \dots, k_{r} ⩾ 0

takich, że

k_{1} + \dots + k_{r} = n

(\binom{n}{k_{1}, \dots, k_{r}}) = (\binom{n}{k_{1}}) (\binom{n - k_{1}}{k_{2}}) (\binom{n - (k_{1} + k_{2})}{k_{3}}) \cdot \dots \cdot (\binom{n - (k_{1} + \dots + k_{r - 1})}{k_{r}}) .

Dowód [Uzupelnij]

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 $(\binom{n}{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 $(\binom{n - k_{1}}{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 $(\binom{n - (k_{1} + k_{2})}{k_{3}})$ sposobów,

...

wyborze $k_{r}$ obiektów spośród pozostałych $n - (k_{1} + \dots + k_{r - 1}) = k_{r}$

i umieszczeniu ich w ostatnim pudełku -- możemy to uczynić na $(\binom{n - (k_{1} + \dots + k_{r - 1})}{k_{r}}) = (\binom{k_{r}}{k_{r}}) = 1$ sposobów.

Zatem wszystkich możliwych rozmieszczeń zgodnie z wymogami z definicji współczynnika multimianowego jest dokładnie $(\binom{n}{k_{1}}) (\binom{n - k_{1}}{k_{2}}) (\binom{n - (k_{1} + k_{2})}{k_{3}}) \cdot \dots \cdot (\binom{n - (k_{1} + \dots + k_{r - 1})}{k_{r}})$ .

Obserwacja 20

Dla

n, k_{1}, \dots, k_{r} ⩾ 0

takich, że

k_{1} + \dots + k_{r} = n

(\binom{n}{k_{1}, \dots, k_{r}}) = \frac{n!}{k_{1}! \cdot \dots \cdot k_{r}!} .

Dowód [Uzupelnij]

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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!}. \endaligned}

Przykład [Uzupelnij]

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:

(\binom{11}{2, 1, 1, 3, 1, 2, 1}) = \frac{11!}{2! \cdot 3! \cdot 2!} = 1663200 .

Przykład [Uzupelnij]

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:

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

łamanych.

Kratka z rysunku o wymiarach $3 \times 4 \times 2$ ma zatem: $(\binom{9}{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 21

Dla

n > 0

, całkowitych

k_{1}, \dots, k_{r}

takich, że

k_{1} + \dots + k_{r} = n

(\binom{n}{k_{1}}) = (\binom{n - 1}{k_{1} - 1, k_{2}, \dots, k_{r}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, \dots, k_{r}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, \dots, k_{r} - 1}) .

Dowód [Uzupelnij]

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 $(\binom{n}{k_{1} - 1, k_{2}, \dots, 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}, \dots, 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 22

(x_{1} + \dots + x_{r})^{n} = \sum_{k_{1} + \dots + k_{r} = n} (\binom{n}{k_{1}, \dots, k_{r}}) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{r}^{k_{r}} .

Matematyka dyskretna 1/Wykład 5: Współczynniki dwumianowe: Różnice pomiędzy wersjami

Wersja z 10:04, 22 sie 2006

Spis treści

Zliczanie podzbiorów raz jeszcze

Dwumiany

Uogólniony współczynnik dwumianowy

Permutacje bez punktów stałych

Współczynniki multimianowe

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

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