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

Aktualna wersja na dzień 22:30, 15 wrz 2023

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

Współczynnik dwumianowy $(\binom{n}{k})$ to liczba $k$ -elementowych podzbiorów zbioru $n$ -elementowego, tzn. $(\binom{n}{k}) = | 𝒫_{k} (ℤ_{n}) |$ . Wyrażenie $(\binom{n}{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ć $(\binom{4}{2})$ wypiszmy wszystkie $2$ -elementowe podzbiory $4$ -elementowego zbioru $ℤ_{4} = {0, 1, 2, 3}$ . Sa to ${0, 1}$ , ${0, 2}$ , ${0, 3}$ , ${1, 2}$ , ${1, 3}$ , ${2, 3}$ ,

skąd

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

.

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

Obserwacja 5.1

Dla $n, k \in ℝ$ 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 $| X | = n ⩾ k ⩾ 0$ . Wtedy funkcja

𝒫_{k} (X) ∋ A \mapsto X m i n u s 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 $| 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 $A = A^{'} \cup {a}$ dla pewnego $A^{'} \in 𝒫_{k - 1} (Z^{'})$ . A zatem

(\binom{n}{k}) = | 𝒫_{k} (Z) | = | 𝒫_{k} (Z^{'}) | + | 𝒫_{k - 1} (Z^{'}) | = (\binom{n - 1}{k}) + (\binom{n - 1}{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 $(\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})$ :

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

Przykład

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.

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

$⟨ (\binom{4}{0}), (\binom{4}{1}), (\binom{4}{2}), (\binom{4}{3}), (\binom{4}{4}) ⟩ = ⟨ 1, 4, 6, 4, 1 ⟩$

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

$⟨ (\binom{5}{5}), (\binom{6}{5}), (\binom{7}{5}), (\binom{8}{5}), \dots ⟩ = ⟨ 1, 6, 21, 56, \dots ⟩$

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ę $ℤ_{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 \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 $k \in {0, \dots, 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:

\begin{aligned} (\binom{n + 1}{k}) & = (\binom{n}{k - 1}) + (\binom{n}{k}) \\ = \frac{n!}{(n - k + 1)! (k - 1)!} + \frac{n!}{(n - k)! k!} \\ = \frac{n!}{(n - k)! (k - 1)!} \cdot (\frac{1}{n - k + 1} + \frac{1}{k}) \\ = \frac{n!}{(n - k)! (k - 1)!} \cdot \frac{k + (n - k + 1)}{(n - k + 1) k} \\ = \frac{(n + 1)!}{(n - k + 1)! k!} \end{aligned}

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.

Ł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 $(\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.

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

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}, \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?

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.

Plik:4.6.mp4

4.6.swf

Obserwacja 5.4 [reguła sumowania po górnym indeksie]

Dla $n, k \in ℕ$ mamy

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

Dowód

Ustalmy $(n + 1)$ -elementowy zbiór $X = {x_{0}, \dots, 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ż $X = {x_{0}, \dots, 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}, \dots, 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}, \dots, 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 $i \in {k, \dots, 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})$ .

Plik:4.7.mp4

4.7.swf

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

Dla $n, k \in ℕ$ mamy:

$\sum_{i = 0}^{k} (\binom{n + i}{i}) = (\binom{n + k + 1}{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} (\binom{n + i}{i}) & = \sum_{i = 0}^{k} (\binom{n + i}{(n + i) - i}) = \sum_{i = 0}^{k} (\binom{n + i}{n}) = \sum_{i = n}^{n + k} (\binom{i}{n}) \\ = (\binom{n + k + 1}{n + 1}) = (\binom{n + k + 1}{k}) . \end{aligned}$

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

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

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

MD1-4.8.swf

Wniosek 5.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}$ )

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, \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ę $f : 𝒫 (X) 𝒫 (X)$ , kładąc

f (Y) = {\begin{cases} (X - Y) - {x} & , jeśli x \in̸ Y \subseteq X \\ (X - Y) \cup {x} & , 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

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 $𝒫 (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} \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 5.9

Dla $m, n ⩾ 0$

\sum_{i = 0}^{m} \frac{n}{2} - i \cdot (\binom{n}{i}) = \frac{m + 1}{2} (\binom{n}{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 $r, k \in ℕ$ wartości $(\binom{r}{k})$ pozostają niezmienione. Oczywiście, dla $r \in ℕ$ , 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 5.10

Dla $r \in ℝ ℜ$ i $k \in ℤ$ 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

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 5.11

Dla $r \in ℝ ℜ$ i $k \in ℤ$

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

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:

$(\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 5.12 [reguła negacji górnego indeksu]

Dla $r \in ℝ ℜ$ , $k \in ℤ$ :

$(- 1)^{k} (\binom{r}{k}) = (\binom{k - r - 1}{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 \dots \cdot (r - k + 1) \\ = (- r) (1 - r) \cdot \dots \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 ℝ ℜ$ , $k \in ℤ$

\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 5.14

Dla $r \in ℝ ℜ$ , $m \in ℤ$

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

Dowód

\begin{aligned} \sum_{i ⩽ m} (- 1)^{i} (\binom{r}{i}) & = \sum_{i ⩽ m} (\binom{i - r - 1}{i}) z reguły negacji górnego indeksu \\ = (\binom{- m + r}{m}) z Obserwacji 5.13 \\ = (- 1)^{m} (\binom{r - 1}{m}) . 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 ℝ ℜ$ , $i, j \in ℤ$

(\binom{r}{i}) (\binom{i}{j}) = (\binom{r}{j}) (\binom{r - j}{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 ⩽ i < j$ . Wtedy:

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

Obserwacja 5.16 [reguła odwracania]

Dla funkcji $f, g : ℤ ℝ ℜ$

f (n) = \sum_{i \in ℤ} (\binom{n}{i}) (- 1)^{i} g (i)

wtedy i tylko wtedy, gdy

g (n) = \sum_{i \in ℤ} (\binom{n}{i}) (- 1)^{i} f (i)

Dowód

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

\begin{aligned} \sum_{i} (\binom{n}{i}) (- 1)^{i} f (i) & = \sum_{i \in ℤ} (\binom{n}{i}) (- 1)^{i} \sum_{j \in ℤ} (\binom{i}{j}) (- 1)^{j} g (j) \\ = \sum_{j \in ℤ} g (j) \sum_{i \in ℤ ℤ} (\binom{n}{i}) (\binom{i}{j}) (- 1)^{i + j} \\ = \sum_{j \in ℤ} g (j) \sum_{i \in ℤ ℤ} (\binom{n}{j}) (\binom{n - j}{i - j}) (- 1)^{i + j} \\ = \sum_{j \in ℤ} g (j) (\binom{n}{j}) \sum_{i \in ℤ} (\binom{n - j}{i - j}) (- 1)^{i + j} \\ = \sum_{j \in ℤ} g (j) (\binom{n}{j}) \sum_{i \in ℤ} (\binom{n - j}{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 $\sum_{i \in ℤ} (\binom{n - j}{i}) (- 1)^{i}$ jest niezerowa (i wynosi $1$ ) tylko dla $j = n$ . Zatem kontynuując:

\begin{aligned} = \sum_{j \in ℤ} g (j) (\binom{n}{j}) \sum_{i \in ℤ} (\binom{n - j}{i}) (- 1)^{i} \\ = g (n) (\binom{n}{n}) = g (n) . \end{aligned}

Permutacje bez punktów stałych

Nieporządek na zbiorze $X$ to permutacja $α : X \to X$ taka, że $α (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 $ℤ_{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 & 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 5.17

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

Dowód

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

n! = \sum_{i = 0}^{n} (\binom{n}{i})! i = \sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) (- 1)^{i} (! i)

Stosując teraz regułę odwracania, dostajemy:

\begin{aligned} ! n & = \sum_{i = 0}^{n} (- 1)^{n - i} (\binom{n}{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} + \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 $n \in ℤ$ , $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 5.18

Dla $n \in ℤ$ , $k, l, k_{1}, \dots, k_{r} \in ℤ$ 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 ${1, 2, \dots, r}$ .

Następna obserwacja wymaga krótkiego uzasadnienia.

Obserwacja 5.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

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}})

.

Wniosek 5.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

\begin{aligned} (\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}}) \\ = \frac{n!}{(n - k_{1})! k_{1}!} \cdot \frac{(n - k_{1})!}{(n - (k_{1} + k_{2}))! k_{2}!} \cdot \dots \cdot \frac{(n - (k_{1} + \dots + k_{r - 1}))!}{(n - (k_{1} + \dots + k_{r}))! k_{r}!} \\ = \frac{n!}{k_{1}! \cdot \dots \cdot k_{r}! \cdot (n - (k_{1} + \dots + k_{r}))!} \\ = \frac{n!}{k_{1}! \cdot \dots \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:

(\binom{11}{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:

(\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 5.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

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

Aktualna wersja na dzień 22:30, 15 wrz 2023

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==
+[[grafika:Ettingshausen-portret.jpg|thumb|right||Andreas Freiherr von Ettingshausen (1796-1878) <br>[[Biografia Ettingshausena|Zobacz biografię]]]]
+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>.
-Wiemy już, że dowolny zbiór <math>n</math>-elementowy ma dokładnie <math>2^n</math> podzbiorów.
+{{kotwica|wspoldwu|'''Współczynnik dwumianowy'''}} <math>{n\choose k}</math>
-Teraz zajmiemy się pytaniem ile taki zbiór ma podzbiorów o dokładnie <math>k</math> elementach.
+to liczba <math>k</math>-elementowych podzbiorów zbioru <math>n</math>-elementowego, tzn. <math>{n\choose k} = {|{\mathcal P}_k(\mathbb{Z}_n)|}</math>. Wyrażenie <math>{n\choose k}</math> czytamy <math>n</math> po <math>k</math>.
-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>
+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 [[#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 [[#tw_5.7|Twierdzeniu 5.7]]
-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>.
-<font color=red>{foto,notka Ettinghausen}</font>
+{{przyklad|||
-Prawdopodobnie jako pierwszy tej notacji użył Albert von Ettinghausen w 1826.
+Aby policzyć <math>{4\choose 2}</math> wypiszmy wszystkie <math>2</math>-elementowe podzbiory <math>4</math>-elementowego zbioru <math>\mathbb{Z}_4=\{0,1,2,3\}</math>. Sa to
-Jednak liczby te już wcześniej pojawiały się wielokrotnie,
+<math>\{0,1\}</math>, <math>\{0,2\}</math>, <math>\{0,3\}</math>, <math>\{1,2\}</math>, <math>\{1,3\}</math>, <math>\{2,3\}</math>,
-choćby w <font color=red>{Trójkącie Pascala}</font>.
+skąd <math>{4\choose 2}=6</math>.}}
-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]||}}
-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
-<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>.
 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 \mathbb{R}</math> zachodzi:
-Dla <math>n,k \in \natur \mathbb{R}</math> zachodzi:
 * <math>{n\choose 0}={n\choose n}=1</math>,
@@ Linia 44: / Linia 29: @@
 }}
-{{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>|{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)
+<center><math>{\mathcal P}_k(X)\ni A \mapsto Xminus 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 47: @@
 }}
-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}.
+<center><math>{n\choose k}={n-1\choose k-1}+{n-1\choose k}</math></center>
-</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>|{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 \{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)|}
+<center><math>{n \choose k} = {|{\mathcal P}_k(Z)|}
-= \abs{|{\mathcal P}_k(Z')|} + \abs{|{\mathcal P}_{k-1}(Z')|}
+= {|{\mathcal P}_k(Z')|} + {|{\mathcal P}_{k-1}(Z')|}
-= {n-1\choose k}+{n-1\choose k-1}.
+= {n-1\choose k}+{n-1\choose k-1}
 </math></center>
 }}
+[[grafika:Pascal-portret.jpg|thumb|right||Blaise Pascal (1623-1662)<br>[[Biografia Pascal|Zobacz biografię]]]]
-<font color=red>{Trójkąt Pascala}</font>
+{{kotwica|trojPas|'''Trójkąt Pascala'''}} (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 85: @@
 * 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>
+<center>
 {| border=1
-|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
+|+ <span style="font-variant:small-caps"></span>
 |-
 |  ||     ||     ||     ||     || <math>0\choose 0</math>   ||     ||     ||     ||     ||
@@ Linia 141: / Linia 107: @@
 |}
+</center>
+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>:
-Przesunięcie w wierszach,
+<center>
-pozwala wyliczyć <math>{n \choose k}</math> jako sumę <math>{n-1 \choose k-1} + {n-1 \choose k}</math>
+<div class="thumb"><flashwrap>file=Trojkat pascala.swf|size=large</flashwrap></div>
-dwu liczb stojących bezpośrednio nad <math>{n \choose k}</math>:
+</center>
-{| border=1
+{{przyklad|||
-|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
+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.
-|-
-|  ||     ||     ||     ||     || 1   ||     ||     ||     ||     ||
-|-
-|  ||     ||     ||     || 1   ||     || 1   ||     ||     ||     ||
-|-
-|  ||     ||     || 1   ||     || 2   ||     || 1   ||     ||    ||
-|-
-|  ||     || 1   ||     || 3   ||     || 3   ||     || 1   ||     ||
-|-
-|  || 1   ||     || 4   ||     || 6   ||     || 4   ||     || 1   ||
-|-
-| 1    ||     || 5   ||     || 10  ||     || 10  ||     || 5   ||     || 1
-|-
-|  || ...   ||     || ...   ||     || ...   ||     || ...   ||     || ...   ||
-|-
-|
-|}
+W trójkącie Pascala współczynniki o tym samym górnym indeksie, np.
-{{przyklad|[Uzupelnij]||}}
-Napisz program drukujący trójkąt Pascala, ale z liczbami <math>{n \choose k}</math> modulo <math>2</math>,
+<center>
-tzn. w miejsce <math>{n \choose k}</math> wstaw jedynie resztę <math>0</math> lub <math>1</math>
+<math>\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
-z dzielenia liczby <math>{n \choose k}</math> przez <math>2</math>.
+</math>
-Zaobserwuj na wydruku powstały fraktal. Wyjaśnij dlaczego tak się dzieje.
+</center>}}
-<font color=red>{Rys. 4.1 Szkic na kartce.}</font>
+tworzą {{kotwica|wiersz|'''wiersz'''}}; natomiast współczynniki o ustalonym dolnym indeksie, np.
-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
+<center>
-</math></center>
+<math>\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</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
-</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 [[#obs_5.1|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|obs 5.3|
 Dla dowolnych <math>0\leqslant k\leqslant n</math>
-<center><math>{n\choose k}=\frac{n!}{(n-k)!k!}.
+<center>
-</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}_k 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\{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>.
+<center><math>\begin{align}{n+1\choose k}&={n\choose k-1}+{n\choose k}\\
-Jeśli <math>k=0</math> to <math>{n+1\choose k}=1=\frac{n!}{(n-0)!0!}</math>.
+&=\frac{n!}{(n-k+1)!(k-1)!}+\frac{n!}{(n-k)!k!}\\
-Załóżmy więc, że <math>k>0</math>. Wtedy:
+&=\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{align}</math></center>
-<center><math>\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</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.
+<center><math>{15\choose 3}=\frac{15!}{(15-3)!3!}=\frac{13\cdot14\cdot15}{2\cdot3}=13\cdot7\cdot5=455
 </math></center>
+}}
-{{przyklad|[Uzupelnij]||}}
+[[File:MD1-4.2.svg|250x100px|thumb|right|MD1-4.2.swf]]
-Wyobraźmy sobie, że znajdujemy się w mieście
+[[File:MD1-4.3.svg|250x100px|thumb|right|MD1-4.3.swf]]
-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>
+{{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.
-Łatwo zauważyć, że jest wiele najkrótszych dróg prowadzących z <math>A</math> do <math>B</math>.
+Ł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.
-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>
+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>.
-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ń,
+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ą?
-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>
+Widzimy, że musimy narysować <math>m+n</math> odcinków jednostkowych,
-i chcemy narysować najkrótszą łamaną po krawędziach kratki
+z których dokładnie <math>m</math> jest pionowych i dokładnie <math>n</math> jest poziomych. Zatem jest
-łączącą lewy dolny wierzchołek z prawym górnym.
-Na ile sposobów możemy narysować taką łamaną?
-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]||}}
+[[File:4.4-4.5.mp4|250x250px|thumb|right|4.4-4.5.swf]]
+{{przyklad|||
 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?
+<center>
+<math>x_0+x_1+x_2+x_3+x_4=7
+</math>
+</center>
-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:
-<font color=red>{4.4 Szkic na kartce.}</font>
+gdzie <math>x_i</math> są liczbami naturalnymi?
-<font color=red>{4.5 Szkic na kartce.}</font>
+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 - animacja obok.
 Zatem istnieje <math>{7+4\choose 4}=330</math> rozwiązań naszego równania.
@@ Linia 318: / Linia 234: @@
 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>,
+<center>
-ile jest łamanych w kratce <math>k \times n</math>,
+<math>x_0+x_1+\ldots+x_{k-1}=n
-czyli <math>{n+k-1\choose n}={n+k-1\choose k-1} </math>.
+</math>
+</center>
-{{przyklad|[Uzupelnij]||}}
+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>.}}
+[[File:SW 6.1.svg|250x100px|thumb|right|SW 6.1.swf]]
+[[File:SW 6.2.svg|250x200px|thumb|right|SW 6.2.swf]]
+{{przyklad|||
+Ile rozwiązań ma równanie
-Ile rozwiązań ma równanie
-<center><math>x_0+\ldots+x_{k-1}=n,
+<center>
-</math></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>.
+<center>
-Na podstawie poprzedniego przykładu poszukiwanych rozwiązań jest zatem <math>n-1 \choose k-1</math>.
+<math>y_0+\ldots+y_{k-1}=n-k
-Rozważmy <math>n</math> obiektów (np. punktów) ustawionych w ciągu jeden przy drugim.
+</math>
+</center>
-<font color=red>{6.1 Szkic na kartce.}</font>
-Separatorem nazywamy pionową kreskę położoną pomiędzy dwoma punktami.
+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>.
-Zatem pomiędzy <math>n</math> punktami mamy <math>n-1</math> możliwych pozycji dla separatora.
+Rozważmy <math>n</math> obiektów (np. punktów) ustawionych w ciągu jeden przy drugim.
-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>
+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:
-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>.
+[[File:MD1-4.11.svg|250x150px|thumb|right|MD1-4.11.swf]]
-{{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>,
+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.
-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>
+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
-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.
-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)|
+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.
-Dla <math>n,k\in\natur\mathbb{N}</math> mamy
+[[File:4.6.mp4|250x250px|thumb|right|4.6.swf]]
-<center><math>\sum_{i=0}^{n}{i\choose k}={n+1\choose k+1}.
+{{obserwacja|5.4 [reguła sumowania po górnym indeksie]|obs 5.4|
-</math></center>
+Dla <math>n,k\in\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>
+{{dowod|||
+Ustalmy <math>(n+1)</math>-elementowy zbiór <math>X=\{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=\{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>\{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>\{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\{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)|
+[[File:4.7.mp4|250x250px|thumb|right|4.7.swf]]
-Dla <math>n,k\in\natur\mathbb{N}</math> mamy:
+{{obserwacja|5.5 [reguła sumowania równoległego]|obs 5.5|
+Dla <math>n,k\in\mathbb{N}</math> mamy:
-<center><math>\sum_{i=0}^{k}{n+i\choose i}={n+k+1\choose k}.
+<center>
-</math></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>
+{{dowod|||
+Tożsamość tę udowodnimy wykorzystując dwukrotnie {regułę symetrii} oraz {regułę sumowania po górnym indeksie}:
-{{dowod|[Uzupelnij]||
-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}
+<center>
+<math>\begin{align}\sum_{i=0}^{k}{n+i\choose i}&=\sum_{i=0}^k{n+i\choose (n+i)-i}
 =\sum_{i=0}^k{n+i\choose n}
 =\sum_{i=n}^{n+k}{i\choose n}\\
-&=&{n+k+1\choose n+1}={n+k+1\choose k}.
+&={n+k+1\choose n+1}={n+k+1\choose k}.
-\endaligned</math></center>
+\end{align}</math>
+</center>
 }}
-{{obserwacja|6|(tożsamość Cauchy'ego, splot Vandermonde'a)|
+{{obserwacja|5.6 [tożsamość Cauchy'ego, splot Vandermonde'a]|obs 5.6|
 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}.
+<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>.
 }}
@@ Linia 485: / Linia 366: @@
 ==Dwumiany==
-Poniższe Twierdzenie o Dwumianie wyjaśnia
+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..
-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)|
+{{obserwacja|5.7 [Twierdzenie o Dwumianie]|obs 5.7|
+Dla <math>x,y\in \mathbb{R}</math> i <math>n\in \mathbb{N}</math>
-Dla <math>x,y\in \mathbb{R}</math> i <math>n\in \mathbb{N}</math>
-<center><math>(x+y)^n=\sum_{i=0}^n{n\choose i}x^iy^{n-i}.
+<center><math>(x+y)^n=\sum_{i=0}^n{n\choose i}x^iy^{n-i}</math></center>
-</math></center>
 }}
-{{dowod|[Uzupelnij]||
+{{dowod|||
+Przedstawmy najpierw potęgę <math>(x+y)^n</math> w rozwiniętej formie iloczynu:
-Przedstawmy najpierw potęgę <math>(x+y)^n</math> w rozwiniętej formie iloczynu:
+<center><math>\underbrace{(x+y)\cdot\ldots\cdot(x+y)}_{n\ razy}</math></center>
-<center><math>\underbrace{(x+y)\cdot\ldots\cdot(x+y)}_{n\ razy}.
-</math></center>
 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 <math>x</math>-ów i pewnej liczby <math>y</math>-ów,
+Każdy taki składnik to iloczyn pewnej liczby <math>x</math>-ów i pewnej liczby <math>y</math>-ów, przy czym łącznie iloczyn taki ma <math>n</math> czynników.
-przy czym łącznie iloczyn taki ma <math>n</math> czynników.
+A zatem każdy składnik ma postać <math>x^k y^{n-k}</math>. Powstaje on poprzez wybór <math>k</math> (spośród <math>n</math>) czynników w iloczynie <math>(x+y)\cdot\ldots\cdot(x+y)</math>, z których do składnika postaci <math>x^k y^{n-k}</math> wchodzi <math>x</math> (a tym samym <math>(n-k)</math> składników, z których wchodzi <math>y</math>). Tym samym składników postaci <math>x^k y^{n-k}</math> jest tyle, ile <math>k</math>-elementowych podzbiorów zbioru <math>n</math>-elementowego, czyli <math>x^k y^{n-k}</math> pojawi się w sumie <math>{n\choose k}</math>-krotnie.
-A zatem każdy składnik ma postać <math>x^k y^{n-k}</math>.
-Powstaje on poprzez wybór <math>k</math> (spośród <math>n</math>)
-czynników w iloczynie <math>(x+y)\cdot\ldots\cdot(x+y)</math>, z których do składnika
-postaci <math>x^k y^{n-k}</math> wchodzi <math>x</math> (a tym samym <math>(n-k)</math> składników, z których wchodzi <math>y</math>).
-Tym samym składników postaci <math>x^k y^{n-k}</math> jest tyle, ile <math>k</math>-elementowych podzbiorów
-zbioru <math>n</math>-elementowego, czyli <math>x^k y^{n-k}</math> pojawi się  w sumie <math>{n\choose k}</math>-krotnie.
 }}
-Twierdzenie o Dwumianie można też udowodnić za pomocą indukcji,
+Twierdzenie o Dwumianie można też udowodnić za pomocą indukcji, co pozostawiamy jako ćwiczenie.
-co pozostawiamy jako ćwiczenie.
+{{przyklad|||
-{{przyklad|[Uzupelnij]||
+<center><math>\begin{align}(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.
+\end{align}</math></center>
-<center><math>\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</math></center>
 }}
-{{wniosek|8|wni 8| Dla dowolnego <math>n\geqslant0</math>
+[[File:MD1-4.8.mp4|250x250px|thumb|right|MD1-4.8.swf]]
+{{wniosek|5.8|wn 5.8|
+Dla dowolnego <math>n\geqslant0</math>
 * <math>(1+x)^n=\sum_{i=0}^n{n\choose i}x^i</math>,
@@ Linia 535: / Linia 411: @@
 * <math>{n\choose 0}+{n\choose 1}+\ldots+{n\choose n}=2^n</math>,
-* <math>{n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0^n</math>.
+* <math>{n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0^n</math>. (Uwaga: <math>{0\choose0}=1=0^0</math>)
-{ (Uwaga: <math>{0\choose0}=1=0^0</math>)}
 }}
-<font color=red>{4.8 Szkic na kartce.}</font>
+{{dowod|||
+Wszystkie punkty wynikają trywialnie z Twierdzenia o Dwumianie. (Pierwszy jest oczywisty. Dla dwu pozostałych zauważmy jedynie, że <math>(1+1)^n=2^n</math>, <math>(1-1)^n=0</math>.) Jednak drugi i trzeci punkt mają ładną interpretację kombinatoryczną.
-{{dowod|[Uzupelnij]||
+Istotnie, liczba podzbiorów zbiorów <math>n</math> elementowego to <math>2^n</math>. Z drugiej strony licząc te podzbiory, możemy kolejno zliczać
+podzbiory <math>0,1,2,\ldots</math>-elementowe - jest ich <math>{n\choose 0},{n\choose 1},{n\choose 2},\ldots</math>.
-Wszystkie punkty wynikają trywialnie z Twierdzenia o Dwumianie.
+Nieco dłuższy jest argument kombinatoryczny dla naprzemiennej sumy
-(Pierwszy jest oczywisty.
+<math>{n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0</math>. Dla <math>n=0</math> jest to oczywiste. Natomiast dla <math>n>0</math> jest to równoważne stwierdzeniu, że dla <math>n</math>-elementowego zbioru <math>X</math>
-Dla dwu pozostałych zauważmy jedynie, że <math>(1+1)^n=2^n</math>, <math>(1-1)^n=0</math>.)
-Jednak drugi i trzeci punkt mają ładną interpretację kombinatoryczną.
-Istotnie, liczba podzbiorów zbiorów <math>n</math> elementowego to <math>2^n</math>.
+* liczba podzbiorów zbioru <math>X</math> o parzystej liczbie elementów jest równa liczbie podzbiorów <math>X</math> o nieparzystej liczbie elementów.
-Z drugiej strony licząc te podzbiory, możemy kolejno zliczać
-podzbiory <math>0,1,2,\ldots</math>-elementowe --
-jest ich <math>{n\choose 0},{n\choose 1},{n\choose 2},\ldots </math>.
-Nieco dłuższy jest argument kombinatoryczny dla naprzemiennej sumy
+Załóżmy najpierw, że <math>n</math> jest nieparzyste. Wtedy każdy podzbiór zbioru <math>X</math> o parzystej liczbie elementów ma dopełnienie o nieparzystej liczbie elementów, a każdy podzbiór zbioru <math>X</math> o nieparzystej liczbie elementów ma dopełnienie o parzystej liczbie elementów.
-<math>{n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0</math>.
+Ta bijektywna odpowiedniość dowodzi, że w istocie jest ich tyle samo.
-Dla <math>n=0</math> jest to oczywiste.
-Natomiast dla <math>n>0</math> jest to równoważne stwierdzeniu,
-że dla <math>n</math>-elementowego zbioru <math>X</math>
-* liczba podzbiorów zbioru <math>X</math> o parzystej liczbie elementów jest równa
+Załóżmy zatem, że <math>n</math> jest parzyste i ustalmy <math>x\in X</math>.
-liczbie podzbiorów <math>X</math> o nieparzystej liczbie elementów.
+Zdefiniujmy funkcję <math>f:\mathcal{P}(X)\mathcal{P}(X)</math>, kładąc
-Załóżmy najpierw, że <math>n</math> jest nieparzyste.
-Wtedy każdy podzbiór zbioru <math>X</math> o parzystej liczbie elementów
-ma dopełnienie o nieparzystej liczbie elementów,
-a każdy podzbiór zbioru <math>X</math> 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 <math>n</math> jest parzyste i ustalmy <math>x\in X</math>.
+<center><math>f(Y)= \begin{cases}
-Zdefiniujmy funkcję <math>f:\mathcal{P}(X)\map\mathcal{P}(X)</math>, kładąc
+(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}</math></center>
-<center><math>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}</math></center>
-Zauważmy, że <math>f</math> jest permutacją <math>\mathcal{P}(X)</math>.
+Zauważmy, że <math>f</math> jest permutacją <math>\mathcal{P}(X)</math>. Rzeczywiście, dla różnych podzbiorów <math>Y_1,Y_2\subseteq X</math> mamy:
-Rzeczywiście, dla różnych podzbiorów <math>Y_1,Y_2\subseteq X</math> mamy:
 * jeśli <math>x\notin Y_1</math> i <math>x\notin Y_2</math> to
-<center><math>f(Y_1)=(X-Y_1)-\set\{x\}=X-Y_1\neq X-Y_2=(X-Y_2)-\set\{x\}=f(Y_2),
+<center><math>f(Y_1)=(X-Y_1)-\{x\}=X-Y_1\neq X-Y_2=(X-Y_2)-\{x\}=f(Y_2)</math>,</center>
-</math></center>
 * jeśli <math>x\in Y_1</math> i <math>x\in Y_2</math> to
-<center><math>f(Y_1)=(X-Y_1)\cup\set\{x\}\neq(X-Y_1)\cup\set\{x\}=f(Y_2),
+<center><math>f(Y_1)=(X-Y_1)\cup\{x\}\neq(X-Y_1)\cup\{x\}=f(Y_2)</math>,</center>
-</math></center>
 * jeśli <math>x\in Y_1</math> i <math>x\notin Y_2</math> to <math>x\in f(Y_1)</math> i <math>x\notin f(Y_2)</math>, zatem <math>f(Y_1)\neq f(Y_2)</math>.
-To dowodzi, że <math>f</math> jest injekcją. Dla dowodu surjektywności weźmy dowolne <math>Z\subseteq X</math>. Jeśli <math>x\in Z</math> to <math>f((X-Z)\cup\set\{x\})=Z</math>, jeśli zaś <math>x\notin Z</math> to <math>f((X-Z)-\set\{x\})=Z</math>. Zatem <math>f</math> jest permutacją zbioru <math>\mathcal{P}(X)</math>. Co więcej łatwo zauważyć, że dla <math>Y</math> o parzystej (nieparzystej) liczbie elementów <math>f(Y)</math> ma nieparzystą (parzystą) liczbę elementów. To dowodzi, że dla parzystego <math>n</math> podzbiorów <math>X</math> o parzystej liczbie elementów jest tyle samo co podzbiorów <math>X</math> o nieparzystej liczbie elementów.
+To dowodzi, że <math>f</math> jest injekcją. Dla dowodu surjektywności weźmy dowolne <math>Z\subseteq X</math>. Jeśli <math>x\in Z</math> to <math>f((X-Z)\cup\{x\})=Z</math>, jeśli zaś <math>x\notin Z</math> to <math>f((X-Z)-\{x\})=Z</math>. Zatem <math>f</math> jest permutacją zbioru <math>\mathcal{P}(X)</math>. Co więcej łatwo zauważyć, że dla <math>Y</math> o parzystej (nieparzystej) liczbie elementów <math>f(Y)</math> ma nieparzystą (parzystą) liczbę elementów. To dowodzi, że dla parzystego <math>n</math> podzbiorów <math>X</math> o parzystej liczbie elementów jest tyle samo co podzbiorów <math>X</math> o nieparzystej liczbie elementów.
 }}
 ==Uogólniony współczynnik dwumianowy==
-Wniosek <font color=red>{[##wniosek - suma i naprzemienna suma wiersza|Uzupelnic wniosek - suma i naprzemienna suma wiersza|]}</font> pozwala na ustalenie
+[[#wn_5.8|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.
-wartość sumy całego wiersza w Trójkącie Pascala i
+W praktyce często pojawia się konieczność (naprzemiennego) sumowania tylko pewnego fragmentu takiego wiersza.Do tego pomocne mogłyby być sumy postaci:
-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:
-<center><math>\begin{array} {lclc}
+<center><math>\begin{array} {lllc}
-\sum_{i=0}^m{n\choose i}&=&{n\choose0}+{n\choose1}+\ldots+{n\choose m}&\qquad(*)\\
+\sum_{i=0}^m{n\choose i}&={n\choose0}+{n\choose1}+\ldots+{n\choose m}&\qquad(*)\\
-\sum_{i=0}^m(-1)^i{n\choose i}&=&{n\choose0}-{n\choose1}+\ldots+(-1)^m{n\choose m}&\qquad(**)
+\sum_{i=0}^m(-1)^i{n\choose i}&={n\choose0}-{n\choose1}+\ldots+(-1)^m{n\choose m}&\qquad(**)
 \end{array}
 </math></center>
 dla <math>0\leqslant m<n</math>.
-Niestety nie jest znana żadna zwarta postać <math>(*)</math>.
+Niestety nie jest znana żadna zwarta postać <math>(*)</math>. 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.
-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|obs 9| Dla <math>m,n\geqslant0</math>
+{{obserwacja|5.9|obs 5.9|
+Dla <math>m,n\geqslant0</math>
+<center><math>\sum_{i=0}^m{\frac{n}{2}-i}\cdot{n\choose i}=\frac{m+1}{2}{n\choose m+1}</math></center>
-<center><math>\sum_{i=0}^m\brackets{\frac{n}{2}-i}\cdot{n\choose i}=\frac{m+1}{2}{n\choose m+1}.
-</math></center>
 }}
-Natomiast naprzemienna częściowa suma <math>(**)</math> 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 <math>r^{\underline{k}}</math>.
+Natomiast naprzemienna częściowa suma <math>(**)</math> 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 <math>r^{\underline{k}}</math>.
+{{kotwica|uwspoldwu|'''Uogólniony współczynnik dwumianowy'''}} <math>{r\choose k}</math> dla <math>r\in\mathbb{R}</math> i <math>k\in\mathbb{Z}</math> to:
-<font color=red>{Uogólniony współczynnik dwumianowy}</font>
-<math>{r\choose k}</math> dla <math>r\in\mathbb{R}</math> i <math>k\in\mathbb{Z}</math> to:
 <center><math>{r\choose k} = \begin{cases} \frac{r(r-1)\cdot\ldots\cdot(r-k+1)}{k(k-1)\cdot\ldots\cdot1}=\frac{r^{\underline{k}}}{k!}, &\mbox{dla }{k\geqslant0},\\0,& \mbox{dla }{k<0}. \end{cases}</math></center>
-Zauważmy, że w istocie dla <math>r,k\in\mathbb{N}\natur</math> wartości <math>{r\choose k}</math> pozostają niezmienione.
-Oczywiście, dla <math>r\in\mathbb{N}\natur</math>, interpretacja <math>{r\choose k}</math>
-jako <math>k</math>-elementowych liczby podzbiorów zbioru <math>r</math>-elementowego pozostaje w mocy.
-Nie jest natomiast znana sensowna kombinatoryczna interpretacja
-uogólnionego współczynnika dwumianowego dla pozostałych rzeczywistych wartosci <math>r</math>.
-Odnotujmy tylko, że <math>{r\choose k}</math> jest wielomianem <math>k</math>-tego stopnia zmiennej <math>r</math>.
-Sporo własności współczynnika dwumianowego przenosi się na wersję uogólnioną.
-Poniższe zostawiamy bez dowodu jako ćwiczenie.
-{{obserwacja|10|obs 10| Dla <math>r\in\mathbb{R}\real</math> i <math>k\in\mathbb{Z}\integer</math> mamy
+Zauważmy, że w istocie dla <math>r,k\in\mathbb{N}</math> wartości <math>{r\choose k}</math> pozostają niezmienione. Oczywiście, dla <math>r\in\mathbb{N}</math>, interpretacja <math>{r\choose k}</math> jako <math>k</math>-elementowych liczby podzbiorów zbioru <math>r</math>-elementowego pozostaje w mocy. Nie jest natomiast znana sensowna kombinatoryczna interpretacja uogólnionego współczynnika dwumianowego dla pozostałych rzeczywistych wartosci <math>r</math>. Odnotujmy tylko, że <math>{r\choose k}</math> jest wielomianem <math>k</math>-tego stopnia zmiennej <math>r</math>. Sporo własności współczynnika dwumianowego przenosi się na wersję uogólnioną. Poniższe zostawiamy bez dowodu jako ćwiczenie.
+{{obserwacja|5.10|obs 5.10|
+Dla <math>r\in\mathbb{R}\real</math> i <math>k\in\mathbb{Z}</math> mamy
 * <math>{r\choose0}=1</math>,
@@ Linia 650: / Linia 502: @@
 }}
-{{przyklad|[Uzupelnij]||
+{{przyklad|||
+Z uwagi na to, że w indeksie dolnym mogą występować jedynie liczby całkowite,
+nie ma sensu reguła symetrii <math>{r \choose k}= {r \choose k-1}</math>. Ale nawet dla całkowitych wartości <math>r</math> zawodzi:
-Z uwagi na to, że w indeksie dolnym mogą występować jedynie liczby całkowite,
-nie ma sensu {reguła symetrii} <math>{r \choose k}= {r \choose k-1}</math>.
-Ale nawet dla całkowitych wartości <math>r</math> zawodzi:
-<center><math>{-1\choose k}\neq{-1\choose -1-k}, \qquad\mbox{dla dowolnych }{k}.</math></center>
+<center><math>{-1\choose k}\neq{-1\choose -1-k}, \qquad\mbox{dla dowolnych }{k}</math>.</center>
 * jeśli <math>k<0</math>, to <math>{-1\choose k}\neq{-1\choose -1-k}=(-1)^{-1-k+1}</math>,
@@ Linia 664: / Linia 515: @@
 }}
-Zachowana jest natomiast <font color=red>{reguła dodawania}</font>.
+Zachowana jest natomiast reguła dodawania.
+{{obserwacja|5.11|obs 5.11|
+Dla <math>r\in\mathbb{R}\real</math> i <math>k\in\mathbb{Z}</math>
-{{obserwacja|11|obs 11| Dla <math>r\in\mathbb{R}\real</math> i  <math>k\in\mathbb{Z}\integer</math>
-<center><math>{r\choose k}={r-1\choose k}+{r-1\choose k-1}.
+<center><math>{r\choose k}={r-1\choose k}+{r-1\choose k-1}</math></center>
-</math></center>
 }}
-{{dowod|[Uzupelnij]||
+{{dowod|||
+Dla ujemnych wartości <math>k</math> wszystkie współczynniki równe są <math>0</math> i tożsamość trywialnie zachodzi. Niech teraz <math>r\in\mathbb{R}\real</math> i <math>k\geqslant0</math>. Oczywiście różnica
-Dla ujemnych wartości <math>k</math> wszystkie współczynniki równe są <math>0</math>
-i tożsamość trywialnie zachodzi.
-Niech teraz <math>r\in\mathbb{R}\real</math> i <math>k\geqslant0</math>.
-Oczywiście różnica
 <center><math>{r\choose k}-{r-1\choose k}-{r-1\choose k-1}
 </math></center>
-jest wielomianem co najwyżej <math>k</math>.
-Może więc, o ile nie jest wielomianem stale równym zero,
+jest wielomianem co najwyżej <math>k</math>. Może więc, o ile nie jest wielomianem stale równym zero, mieć co najwyżej <math>k</math> miejsc zerowych.
-mieć co najwyżej <math>k</math> miejsc zerowych.
+Z drugiej strony wiemy już, że ta różnica zeruje się dla wszystkich liczb naturalnych <math>r</math>, więc musi być zawsze równa <math>0</math>.
-Z drugiej strony wiemy już,
-że ta różnica zeruje się dla wszystkich liczb naturalnych <math>r</math>,
-więc musi być zawsze równa <math>0</math>.
 }}
-Uogólniona reguła dodawania z Obserwacji <font color=red>{[##obserwacja - uogolniona regula dodawania|Uzupelnic obserwacja - uogolniona regula dodawania|]}</font>
+[[File:4.9.svg|250x250px|thumb|right|4.9.swf]]
-pozwala rozszerzyć Trójkąt Pascala
-na współczynniki o ujemnych wartościach górnego indeksu.
-{Rys. 4.9 Szkic na kartce.}
+Uogólniona reguła dodawania z [[#obs_5.11|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:
-<center><math>{-1\choose 0},{-2\choose0},{-1\choose1},{-3\choose0},{-2\choose 1},{-1\choose2},\ldots.
-</math></center>
-Przyjrzyjmy się wartościom <math>{n\choose k}</math> dla ustalonego <math>k</math> i całkowitych wartości <math>n</math>.
+<center>
-Zauważalny jest pewien rodzaj symetrii między tymi wartościami.
+<math>{-1\choose 0},{-2\choose0},{-1\choose1},{-3\choose0},{-2\choose 1},{-1\choose2},\ldots</math>
-W istocie zachodzi on  dla wszystkich rzeczywistych wartości górnego indeksu.
+</center>
+Przyjrzyjmy się wartościom <math>{n\choose k}</math> dla ustalonego <math>k</math> i całkowitych wartości <math>n</math>. 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]|obs 5.12|
+Dla <math>r\in\mathbb{R}\real</math>, <math>k\in\mathbb{Z}</math>:
-{{obserwacja|12|(reguła negacji górnego indeksu)|
-Dla <math>r\in\mathbb{R}\real</math>, <math>k\in\mathbb{Z}\integer</math>:
+<center>
+<math>(-1)^k{r\choose k}={k-r-1\choose k}</math>
+</center>
-<center><math>(-1)^k{r\choose k}={k-r-1\choose k}.
-</math></center>
 }}
-{{dowod|[Uzupelnij]||
+{{dowod|||
+Policzymy wartość obu stron po uprzednim wymnożeniu przez wspólny mianownik <math>k!</math>:
-Policzymy wartość obu stron po uprzednim wymnożeniu przez wspólny mianownik <math>k!</math>:
-<center><math>\aligned(-1)^k r^{\underline{k}}
+<center><math>\begin{align}(-1)^k r^{\underline{k}}
-&=&(-1)^k r(r-1)\cdot\ldots\cdot(r-k+1)\\
+&=(-1)^k r(r-1)\cdot\ldots\cdot(r-k+1)\\
-&=&(-r)(1-r)\cdot\ldots\cdot(k-1-r)\\
+&=(-r)(1-r)\cdot\ldots\cdot(k-1-r)\\
-&=&(k-r-1)^{\underline{k}}.
+&=(k-r-1)^{\underline{k}}.
-\endaligned</math></center>
+\end{align}</math></center>
 }}
-Znaną nam już z Obserwacji <font color=red>{[##obserwacja - sumowanie rownolegle|Uzupelnic obserwacja - sumowanie rownolegle|]}</font>
+Znaną nam już z [[#obs_5.5|Obserwacji 5.5]] regułę równoległego sumowania możemy uogólnić za pomocą argumentu podobnego do użytego w dowodzie [[#obs_5.11|Obserwacji 5.11]].
-regułę równoległego sumowania możemy uogólnić za pomocą argumentu podobnego do
-użytego w dowodzie Obserwacji <font color=red>{[##obserwacja - uogolniona regula dodawania|Uzupelnic obserwacja - uogolniona regula dodawania|]}</font>.
-{{obserwacja|13|obs 13| Dla <math>r\in\mathbb{R}\real</math>, <math>k\in\mathbb{Z}\integer</math>
+{{obserwacja|5.13|obs 5.13|
+Dla <math>r\in\mathbb{R}\real</math>, <math>k\in\mathbb{Z}</math>
+<center><math>\sum_{i\leqslant k}{r+i\choose i}={r+k+1\choose k}</math></center>
-<center><math>\sum_{i\leqslant k}{r+i\choose i}={r+k+1\choose k}.
-</math></center>
 }}
-Zauważmy, że rozważana suma jest tylko pozornie nieskończona,
+Zauważmy, że rozważana suma jest tylko pozornie nieskończona, gdyż dla wszystkich ujemnych wartości <math>i</math> odpowiednie składniki zerują się.
-gdyż dla wszystkich ujemnych wartości <math>i</math> odpowiednie składniki
+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.
-zerują się.
-W dalszych ciągu przyjmiemy będziemy również rozważać podobne sumy "nieskończone",
+Wyposażeni w regułę negacji górnego indeksu wracamy teraz my do naprzemiennej, cześciowej sumy wierszy w Trójkącie Pascala, czyli do <math>(**)</math>.
-ale przy założeniu, że tylko skończenie wiele składników jest niezerowych.
+{{obserwacja|5.14|obs 5.14|
+Dla <math>r\in\mathbb{R}\real</math>, <math>m\in\mathbb{Z}</math>
-Wyposażeni w regułę negacji górnego indeksu
-wracamy teraz my do naprzemiennej, cześciowej sumy wierszy w Trójkącie Pascala,
-czyli do <math>(**)</math>.
-{{obserwacja|14|obs 14| Dla <math>r\in\mathbb{R}\real</math>, <math>m\in\mathbb{Z}\integer</math>
+<center><math>\sum_{i\leqslant m}(-1)^i{r\choose i}=(-1)^m{r-1\choose m}</math></center>
-<center><math>\sum_{i\leqslant m}(-1)^i{r\choose i}=(-1)^m{r-1\choose m}.
-</math></center>
 }}
-{{dowod|[Uzupelnij]||
+{{dowod|||
+<center><math>\begin{align}\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{align}</math></center>
-<center><math>\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</math></center>
 }}
@@ Linia 771: / Linia 618: @@
 szczególnych permutacji. Zaczniemy od pomocniczej obserwacji.
-{{obserwacja|15|(przestawienie trójmianowe)|
+{{obserwacja|5.15 [przestawienie trójmianowe]|obs 5.15|
-Dla <math>r\in\mathbb{R}\real</math>, <math>i,j\in\mathbb{Z}\integer</math>
+Dla <math>r\in\mathbb{R}\real</math>, <math>i,j\in\mathbb{Z}</math>
+<center><math>{r\choose i}{i\choose j}={r\choose j}{r-j\choose i-j}</math></center>
-<center><math>{r\choose i}{i\choose j}={r\choose j}{r-j\choose i-j}.
-</math></center>
 }}
-{{dowod|[Uzupelnij]||
+{{dowod|||
+Zauważmy, że dla <math>i<j</math> obie strony równości się zerują. Także dla <math>i<0</math> teza jest trywialna. Zatem możemy założyć, że <math>0\leqslant i<j</math>. Wtedy:
-Zauważmy, że dla <math>i<j</math> obie strony równości się zerują. Także dla <math>i<0</math> teza jest trywialna. Zatem możemy założyć, że <math>0\leqslant i<j</math>. Wtedy:
+<center><math>\begin{align}{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{align}</math></center>
-<center><math>\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</math></center>
 }}
-{{obserwacja|16|(reguła odwracania)|
+{{obserwacja|5.16 [reguła odwracania]|obs 5.16|
-Dla funkcji <math>f,g:\mathbb{Z}\integer\map\mathbb{R}\real</math>
+Dla funkcji <math>f,g:\mathbb{Z}\mathbb{R}\real</math>
-<center><math>f(n)=\sum_{i\in\mathbb{Z}\integer}{n\choose i}(-1)^ig(i)
+<center><math>f(n)=\sum_{i\in\mathbb{Z}}{n\choose i}(-1)^ig(i)
 </math></center>
-}}
 wtedy i tylko wtedy, gdy
-<center><math>g(n)=\sum_{i\in\mathbb{Z}\integer}{n\choose i}(-1)^if(i).
-</math></center>
-{{dowod|[Uzupelnij]||
+<center><math>g(n)=\sum_{i\in\mathbb{Z}}{n\choose i}(-1)^if(i)</math></center>
+}}
+{{dowod|||
+Z uwagi na symetrię założeń wystarczy udowodnić tylko jedne implikację. Zakładamy zatem, że <math>f(n)=\sum_{i\in\mathbb{Z}}{n\choose i}(-1)^ig(i)</math> by dostać:
+<center><math>\begin{align}\sum_i{n\choose i}(-1)^if(i)
+&=\sum_{i\in\mathbb{Z}}{n\choose i}(-1)^i\sum_{j\in\mathbb{Z}}{i\choose j}(-1)^jg(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{align}</math></center>
-Z uwagi na symetrię założeń wystarczy udowodnić tylko jedne implikację.
-Zakładamy zatem, że <math>f(n)=\sum_{i\in\mathbb{Z}\integer}{n\choose i}(-1)^ig(i)</math> by dostać:
-<center><math>\aligned\sum_i{n\choose i}(-1)^if(i)
+gdzie druga równość wynika ze zmiana kolejności sumowania, trzecia z przestawienia trójmianowego, a ostatnia przez podstawienie <math>i:=i+j</math>.
-&=&\sum_{i\in\mathbb{Z}\integer}{n\choose i}(-1)^i\sum_{j\in\mathbb{Z}\integer}{i\choose j}(-1)^jg(j)\\
-&=&\sum_{j\in\mathbb{Z}\integer} g(j)\sum_{i\in\mathbb{Z}\mathbb{Z}\integer}{n\choose i}{i\choose j}(-1)^{i+j}\\
-&=&\sum_{j\in\mathbb{Z}\integer} g(j)\sum_{i\in\mathbb{Z}\mathbb{Z}\integer} {n\choose j}{n-j\choose i-j}(-1)^{i+j}\\
-&=&\sum_{j\in\mathbb{Z}\integer} g(j){n\choose j}\sum_{i\in\mathbb{Z}\integer} {n-j\choose i-j}(-1)^{i+j}\\
-&=&\sum_{j\in\mathbb{Z}\integer} g(j){n\choose j}\sum_{i\in\mathbb{Z}\integer} {n-j\choose i}(-1)^i,
-\endaligned</math></center>
-gdzie druga równość wynika ze zmiana kolejności sumowania,
+Z [[#wn_5.8|Wniosku 5.8]] wiemy, że suma <math>\sum_{i\in\mathbb{Z}}{n-j\choose i}(-1)^i</math> jest niezerowa (i wynosi <math>1</math>) tylko dla <math>j=n</math>. Zatem kontynuując:
-trzecia z przestawienia trójmianowego,
-a ostatnia przez podstawienie <math>i:=i+j</math>.
-Z Wniosku <font color=red>{[##wniosek - suma i naprzemienna suma wiersza|Uzupelnic wniosek - suma i naprzemienna suma wiersza|]}</font> wiemy,
-że suma <math>\sum_{i\in\mathbb{Z}\integer}{n-j\choose i}(-1)^i</math> jest niezerowa (i wynosi <math>1</math>)
-tylko dla <math>j=n</math>.
-Zatem kontynuując:
-<center><math>\aligned&=&\sum_{j\in\mathbb{Z}\integer} g(j){n\choose j}\sum_{i\in\mathbb{Z}\integer}{n-j\choose i}(-1)^i\\
+<center><math>\begin{align} &=\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){n\choose n}
 = g(n).
-\endaligned</math></center>
+\end{align}</math></center>
 }}
@@ Linia 835: / Linia 683: @@
 ===Permutacje bez punktów stałych===
-{Nieporządek} na zbiorze <math>X</math> to permutacja <math>\alpha:X\map X</math> taka,
+{{kotwica|nieporz|'''Nieporządek'''}} na zbiorze <math>X</math> to permutacja <math>\alpha:X\to X</math> taka, że <math>\alpha(x)\neq x</math> dla dowolnego <math>x\in X</math>, czyli permutacja "bez punktów stałych".
-że <math>\alpha(x)\neq x</math> dla dowolnego <math>x\in X</math>,
-czyli permutacja "bez punktów stałych".
-{Podsilnia} liczby <math>n</math>, w skrócie <math>\fPodsilnia{n}</math>,
+{{kotwica|podsilnia|'''Podsilnia'''}} liczby <math>n</math>, w skrócie <math>!n</math>, to liczba nieporządków zbioru <math>n</math>-elementowego. Przyjmujemy, że <math>!0=1</math>, jako ze jedyna permutacja zbioru pustego - funkcja pusta - w oczywisty sposób nie ma punktów stałych.
-to liczba nieporządków zbioru <math>n</math>-elementowego.
-Przyjmujemy, że <math>\fPodsilnia{0}=1</math>, jako ze jedyna permutacja zbioru pustego --
-funkcja pusta -- w oczywisty sposób nie ma punktów stałych.
-{{przyklad|[Uzupelnij]||
+{{przyklad|||
+Zbiór <math>\mathbb{Z}_4=\{0,1,2,3\}</math> ma <math>4!=24</math> permutacje, ale tylko <math>9</math> z nich to nieporządki. Oto ich lista:
-Zbiór <math>\mathbb{Z}\integer_4=\set\{0,1,2,3\}</math> ma <math>4!=24</math> permutacje,
-ale tylko <math>9</math> z nich to nieporządki. Oto ich lista:
 <center><math>\begin{array} {cccccccccccccc}
@@ Linia 863: / Linia 705: @@
 \end{array}
 </math></center>
 }}
-{{obserwacja|17|obs 17|
+{{obserwacja|5.17|obs 5.17|
-<math>\fPodsilnia{n} = n!\sum_{i=0}^n\frac{(-1)^i}{i!}</math>.
+<math>!n = n!\sum_{i=0}^n\frac{(-1)^i}{i!}</math>.
 }}
-{{dowod|[Uzupelnij]||
+{{dowod|||
+Zauważmy najpierw, że liczba permutacji <math>\alpha</math> zbioru <math>n</math>-elementowego takich, że <math>\alpha(x)\neq x</math> dla dokładnie <math>i</math> elementów <math>x\in X</math>,
+wynosi <math>{n\choose i}!i</math>. Stąd:
-Zauważmy najpierw, że liczba permutacji <math>\alpha</math> zbioru <math>n</math>-elementowego takich,
-że <math>\alpha(x)\neq x</math> dla dokładnie <math>i</math> elementów <math>x\in X</math>
-wynosi <math>{n\choose i}\fPodsilnia{i}</math>. Stąd:
 <center><math>n!=
-\sum_{i=0}^n {n\choose i}\fPodsilnia{i}
+\sum_{i=0}^n {n\choose i}!i
-=\sum_{i=0}^n (-1)^i{n\choose i}(-1)^i\fPodsilnia{i}.
+=\sum_{i=0}^n (-1)^i{n\choose i}(-1)^i(!i)</math></center>
-</math></center>
+Stosując teraz regułę odwracania, dostajemy:
-Aplikując teraz regułę odwracania dostajemy:
+<center><math>\begin{align}!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{align}</math></center>
-<center><math>\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</math></center>
 }}
 ==Współczynniki multimianowe==
 Współczynniki dwumianowe pojawiały się przy rozwinięciu dwumianu <math>(x+y)^n</math>.
 Odpowiadały one wyborom dwuwartościowym.
@@ Linia 905: / Linia 750: @@
 oczywiście <math>k_1+\ldots k_r=n</math>.
-{Współczynnik multimianowy} <math>{n\choose k_1,k_2\ldots,k_{r}}</math>,
+{{kotwica|wspolmulti|'''Współczynnik multimianowy'''}} <math>{n\choose k_1,k_2\ldots,k_{r}}</math>, dla <math>n\in\mathbb{Z}</math>, <math>r\geqslant2</math> oraz całkowitych <math>k_1,\ldots,k_r</math> takich, że <math>k_1+\ldots k_r=n</math>, to liczba sposobów umieszczenia <math>n</math> obiektów w <math>r</math> pudełkach z odpowiednio <math>k_1</math> obiektami w pierwszym pudełku, <math>k_2</math> w drugim, itd., oraz <math>k_r</math> w <math>r</math>-tym. Jeśli którakolwiek z liczb <math>k_i</math> jest ujemna to współczynnik jest równy <math>0</math>.
-dla <math>n\in\mathbb{Z}\natur</math>, <math>r\geqslant2</math>
+Zauważmy, że z uwagi na symetrię dolnych indeksów, ich kolejność nie jest istotna. Oczywiście <math>{n \choose k}</math> to w nowej notacji <math>{n \choose k,n-k}</math>.
-oraz całkowitych <math>k_1,\ldots,k_r</math> takich, że <math>k_1+\ldots k_r=n</math>,
-to liczba sposobów umieszczenia <math>n</math> obiektów w <math>r</math> pudełkach z odpowiednio
-<math>k_1</math> obiektami w pierwszym pudełku, <math>k_2</math> w drugim, itd.,
-oraz <math>k_r</math> w <math>r</math>-tym.
-Jeśli którakolwiek z liczb <math>k_i</math> jest ujemna to współczynnik jest równy <math>0</math>.
-Zauważmy, że z uwagi na symetrię dolnych indeksów,
-ich kolejność nie jest istotna.
-Oczywiście <math>{n \choose k}</math> to w nowej notacji <math>{n \choose k,n-k}</math>.
 Następna obserwacja wynika wprost z definicji współczynników multimianowych.
-{{obserwacja|18|obs 18| Dla <math>n\in\mathbb{Z}\natur</math>, <math>k,l,k_1,\ldots,k_r\in\mathbb{Z}\integer</math> takich, że <math>k_1+\ldots k_r=n= k+l</math>
+{{obserwacja|5.18|obs 5.18|
-zachodzi:
+Dla <math>n\in\mathbb{Z}</math>, <math>k,l,k_1,\ldots,k_r\in\mathbb{Z}</math> takich, że <math>k_1+\ldots k_r=n= k+l</math> zachodzi:
 * <math>{n\choose n,0,\ldots,0}=1</math>,
@@ Linia 929: / Linia 766: @@
 * <math>{n\choose l,l,0,\ldots,0}={n\choose k}={n\choose l}</math>,
-* <math>{n\choose k_1,\ldots,k_r} = {n\choose k_{\sigma(1)},\ldots,k_{\sigma(r)}}</math>,
+* <math>{n\choose k_1,\ldots,k_r} = {n\choose k_{\sigma(1)},\ldots,k_{\sigma(r)}}</math>, dla dowolnej permutacji <math>\sigma</math> zbioru <math>\{1,2,\ldots,r\}</math>.
-dla dowolnej permutacji <math>\sigma</math> zbioru <math>\set\{1,2,\ldots,r\}</math>.
 }}
@@ Linia 936: / Linia 772: @@
 Następna obserwacja wymaga krótkiego uzasadnienia.
-{{obserwacja|19|obs 19| Dla <math>n,k_1,\ldots,k_r\geqslant0</math> takich, że <math>k_1+\ldots+k_r=n</math>
+{{obserwacja|5.19|obs 5.19|
+Dla <math>n,k_1,\ldots,k_r\geqslant0</math> takich, że <math>k_1+\ldots+k_r=n</math>
 <center><math>{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}.
+\cdot\ldots\cdot{n-(k_1+\ldots+k_{r-1})\choose k_r}</math></center>
-</math></center>
 }}
-{{dowod|[Uzupelnij]||
+{{dowod|||
 Rozmieszczenie <math>n</math>-obiektów w <math>r</math> pudełkach po <math>k_i</math> w każdym, polega na:
-* wyborze <math>k_1</math> obiektów spośród wszystkich <math>n</math>
+* wyborze <math>k_1</math> obiektów spośród wszystkich <math>n</math> i umieszczeniu ich w pierwszym pudełku - możemy to uczynić na <math>{n\choose k_1}</math> sposobów,
-i umieszczeniu ich w pierwszym pudełku
--- możemy to uczynić na <math>{n\choose k_1}</math> sposobów,
-* wyborze <math>k_2</math> obiektów spośród pozostałych <math>n-k_1</math>
+* wyborze <math>k_2</math> obiektów spośród pozostałych <math>n-k_1</math> i umieszczeniu ich w drugim pudełku - możemy to uczynić na <math>{n-k_1\choose k_2}</math> sposobów,
-i umieszczeniu ich w drugim pudełku
--- możemy to uczynić na <math>{n-k_1\choose k_2}</math> sposobów,
 * wyborze <math>k_3</math> obiektów spośród pozostałych <math>n-(k_1+k_2)</math>
-i umieszczeniu ich w trzecim pudełku
+i umieszczeniu ich w trzecim pudełku - możemy to uczynić na <math>{n-(k_1+k_2)\choose k_3}</math> sposobów,
--- możemy to uczynić na <math>{n-(k_1+k_2)\choose k_3}</math> sposobów,
 * ...
-* wyborze <math>k_r</math> obiektów spośród pozostałych <math>n-(k_1+\ldots+k_{r-1})=k_r</math>
+* wyborze <math>k_r</math> obiektów spośród pozostałych <math>n-(k_1+\ldots+k_{r-1})=k_r</math> i umieszczeniu ich w ostatnim pudełku - możemy to uczynić na <math>{n-(k_1+\ldots+k_{r-1})\choose k_r}={k_r\choose k_r}=1</math> sposobów.
-i umieszczeniu ich w ostatnim pudełku
--- możemy to uczynić na <math>{n-(k_1+\ldots+k_{r-1})\choose k_r}={k_r\choose k_r}=1</math> sposobów.
 Zatem wszystkich możliwych rozmieszczeń zgodnie z wymogami z definicji
-współczynnika multimianowego jest dokładnie
+współczynnika multimianowego jest dokładnie <math>{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}</math>.}}
-<math>{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}</math>.
+{{wniosek|5.20|wn 5.20|
-}}
+Dla <math>n,k_1,\ldots,k_r\geqslant0</math> takich, że <math>k_1+\ldots+k_r=n</math>
-{{obserwacja|20|wni 20| Dla <math>n,k_1,\ldots,k_r\geqslant0</math> takich, że <math>k_1+\ldots+k_r=n</math>
+<center><math>{n\choose k_1,\ldots,k_r}=\frac{n!}{k_1!\cdot\ldots\cdot k_r!}</math></center>
-<center><math>{n\choose k_1,\ldots,k_r}=\frac{n!}{k_1!\cdot\ldots\cdot k_r!}.
-</math></center>
 }}
-{{dowod|[Uzupelnij]||
+{{dowod|||
-<center><math>\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}\\
+<center><math>\begin{align}{n\choose k_1,\ldots,k_r}
-&=&\frac{n!}{(n-k_1)!k_1!}\cdot\frac{(n-k_1)!}{(n-(k_1+k_2))!k_2!}
+&={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!\cdot(n-(k_1+\ldots+k_r))!}\\
-&=&\frac{n!}{k_1!\cdot\ldots\cdot k_r!}.
+&=\frac{n!}{k_1!\cdot\ldots\cdot k_r!}.
-\endaligned</math></center>
+\end{align}</math></center>
 }}
-{{przyklad|[Uzupelnij]||
+{{przyklad|||
 Ile liczb możemy ułożyć zapisując w dowolnej kolejności <math>11</math> cyfr: <math>1,1,3,4,5,5,5,6,7,7,9</math>?
-Zauważmy, że każda taka liczba
+Zauważmy, że każda taka liczba powstaje przez wybór dwu pozycji dla cyfry <math>1</math>, jednej dla cyfry <math>3</math>, jednej dla cyfry <math>4</math>, trzech dla cyfry <math>5</math>, jednej dla cyfry <math>6</math>, dwu dla cyfry <math>7</math> i wreszcie jednej pozycji dla cyfry <math>9</math>. Zatem <math>11</math> pozycji to nasze obiekty, które rozmieszczamy w siedmiu pudełkach  etykietowanych cyframi: <math>1,3,4,5,6,7,9</math>. Zatem z definicji współczynnika multimianowego mamy:
-powstaje przez wybór dwu pozycji dla cyfry <math>1</math>,
-jednej dla cyfry <math>3</math>,
-jednej dla cyfry <math>4</math>,
+<center><math>{11\choose 2,1,1,3,1,2,1}=\frac{11!}{2!\cdot3!\cdot2!}=1663200</math></center>
-trzech dla cyfry <math>5</math>,
-jednej dla cyfry <math>6</math>,
-dwu dla cyfry <math>7</math>
-i wreszcie jednej pozycji dla cyfry <math>9</math>.
-Zatem <math>11</math> pozycji to nasze obiekty,
-które rozmieszczamy w siedmiu pudełkach  etykietowanych cyframi: <math>1,3,4,5,6,7,9</math>.
-Zatem z definicji współczynnika multimianowego mamy:
-<center><math>{11\choose 2,1,1,3,1,2,1}=\frac{11!}{2!\cdot3!\cdot2!}=1663200.
-</math></center>
 }}
-{{przyklad|[Uzupelnij]||
+{{przyklad|||
+Rozważmy raz jeszcze podróż w mieście o ulicach na planie siatki. Tym razem jednak... <math>3</math>-wymiarową wersję. Mamy więc do dyspozycji trójwymiarową, prostopadłościenną kratownicę <math>a\times b\times c</math>.
+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 <math>a+b+c</math> odcinków jednostkowych. Przy czym dokładnie <math>a</math> z nich jest poziomych, <math>b</math> pionowych i <math>c</math> idzie w głąb. Zatem najkrótszych łamanych jest tyle co rozmieszczeń <math>a+b+c</math> odcinków (obiekty) w <math>3</math> pudełkach: "poziomy", "pionowy", "w głąb" tak, by w było ich odpowiednio <math>a,b</math> i <math>c</math>. Z definicji współczynnika multimianowego mamy zatem:
-Rozważmy raz jeszcze podróż w mieście o ulicach na planie siatki.
-Tym razem jednak... <math>3</math>-wymiarową wersję.
-Mamy więc do dyspozycji trójwymiarową, prostopadłościenną kratownicę
-<math>a\times b\times c</math>.
-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ę
+<center><math>{a+b+c\choose a,b,c}=\frac{(a+b+c)!}{a!b!c!}</math>,</center>
-z dokładnie <math>a+b+c</math> odcinków jednostkowych.
-Przy czym dokładnie <math>a</math> z nich jest poziomych,
-<math>b</math> pionowych i <math>c</math> idzie w głąb.
-Zatem najkrótszych łamanych jest tyle co rozmieszczeń <math>a+b+c</math> odcinków (obiekty)
-w <math>3</math> pudełkach: "poziomy", "pionowy", "w głąb"
-tak, by w było ich odpowiednio <math>a,b</math> i <math>c</math>.
-Z definicji współczynnika multimianowego mamy zatem:
-<center><math>{a+b+c\choose a,b,c}=\frac{(a+b+c)!}{a!b!c!},
-</math></center>
 łamanych.
 Kratka z rysunku o wymiarach <math>3\times4\times2</math> ma zatem:
 <math>{9\choose3,4,2}=\frac{9!}{3!\cdot4!\cdot2!}=420</math> interesujących nas łamanych.
 }}
@@ Linia 1041: / Linia 851: @@
 Współczynniki multimianowe także zachowują pewną regułę dodawania.
-{{obserwacja|21|obs 21| Dla <math>n>0</math>, całkowitych <math>k_1,\ldots,k_r</math> takich, że <math>k_1+\ldots+k_r=n</math>
+{{obserwacja|5.21|obs 5.21|
+Dla <math>n>0</math>, całkowitych <math>k_1,\ldots,k_r</math> takich, że <math>k_1+\ldots+k_r=n</math>
+<center><math>{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}</math></center>
-<center><math>{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}.
-</math></center>
 }}
-{{dowod|[Uzupelnij]||
+{{dowod|||
+Ponieważ <math>n>0</math>, możemy wybrać i ustalić ulubiony obiekt <math>x</math>. Możemy go umieścić w jednym z <math>r</math> pudełek. Jeśli jednak umieścimy go w pierwszym, to pozostałe <math>n-1</math> obiektów musimy rozłożyć do <math>r</math> pudeł zgodnie z warunkami wyjściowymi, ale do pierwszej szuflady mamy włożyć już <math>1</math> obiekt mniej (<math>k_1-1</math> a nie <math>k_1</math>). Rozłożenia tego możemy dokonać na <math>{n\choose k_1-1,k_2,\ldots,k_r}</math>. Analogicznie gdy <math>x</math> umieścimy w drugim pudle, to pozostałe przedmioty rozkładamy w pudłach odpowiednio po <math>k_1, k_2-1, k_3,\ldots,k_r</math>. Po przesumowaniu po numerach pudła, w którym jest <math>x</math> dostajemy nasz wzór.
-Ponieważ <math>n>0</math>, możemy wybrać i ustalić ulubiony obiekt <math>x</math>.
-Możemy go umieścić w jednym z <math>r</math> pudełek.
-Jeśli jednak umieścimy go w pierwszym,
-to pozostałe <math>n-1</math> obiektów musimy rozłożyć do <math>r</math> pudeł
-zgodnie z warunkami wyjściowymi,
-ale do pierwszej szuflady mamy włożyć już <math>1</math> obiekt mniej (<math>k_1-1</math> a nie <math>k_1</math>).
-Rozłożenia tego możemy dokonać na <math>{n\choose k_1-1,k_2,\ldots,k_r}</math>.
-Analogicznie gdy <math>x</math> umieścimy w drugim pudle,
-to pozostałe przedmioty rozkładamy w pudłach odpowiednio po <math>k_1, k_2-1, k_3,\ldots,k_r</math>.
-Po przesumowaniu po numerach pudła, w którym jest <math>x</math> dostajemy nasz wzór.
 }}
 Jako ćwiczenie pozostawiamy dowód następującego uogólnienia wzoru dwumiennego:
-{{obserwacja|22|obs 22|
+{{obserwacja|5.22|obs 5.22|
 <center><math>(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}.
+{n \choose k_1,\ldots,k_r} x_1^{k_1} x_2^{k_2}\ldots x_r^{k_r}</math></center>
-</math></center>
 }}