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

Zliczanie podzbiorów raz jeszcze

Wiemy już, że dowolny zbiór $n$ -elementowy ma dokładnie $2^{n}$ podzbiorów. Teraz zajmiemy się pytaniem ile taki zbiór ma podzbiorów o dokładnie $k$ elementach. Policzymy zatem liczność rodziny $k$ -elemetowych podzbiorów zbioru $X$ . Rodzinę tę oznaczać będziemy przez $𝒫_{k} (X)$ .

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

{foto,notka Ettinghausen} Prawdopodobnie jako pierwszy tej notacji użył Albert von Ettinghausen w 1826. Jednak liczby te już wcześniej pojawiały się wielokrotnie, choćby w {Trójkącie Pascala}. Sama nazwa "współczynniki dwumianowe" bierze się stąd, że liczby te pojawiają się w rozwinięciu dwumianu $(x + y)^{n}$ . Zobaczymy to dokładnie w Twierdzeniu {[##tw dwumianowe|Uzupelnic tw dwumianowe|]}.

Przykład [Uzupelnic]

Aby policzyć $(\binom{4}{2})$ wypiszmy wszystkie $2$ -elementowe podzbiory $4$ -elementowego zbioru Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle \mathbb{Z}\integer_4=\set\{0,1,2,3\}} . Sa to Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{0,1\}} , Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{0,2\}} , Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{0,3\}} , Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{1,2\}} , Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{1,3\}} , Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{2,3\}} , skąd $(\binom{4}{2}) = 6$ .

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

Obserwacja 1

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

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

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

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

$(\binom{n}{k}) = (\binom{n}{n - k})$ , dla $n ⩾ k ⩾ 0$ .

Dowód [Uzupelnij]

Pierwszy punkt jest natychmiastową konsekwencją faktu, że dowolny zbiór $n$ -elementowy ma tylko jeden $0$ -elementowy podzbiór -- podzbiór pusty i tylko jeden podzbiór $n$ -elementowy -- cały zbiór.

Drugi punkt jest oczywisty, jako że zbiór $n$ -elementowy nie może mieć podzbiorów o $k > n$ elementach.

Dla dowodu trzeciego punktu, zauważmy jedynie, że podzbiorów jednoelementowych jest dokładnie tyle ile elementów w zbiorze.

Wreszcie dla dowodu ostatniego punktu załóżmy, że Parser nie mógł rozpoznać (nieznana funkcja „\abs”): {\displaystyle \abs|{X}|=n\geqslant k\geqslant 0} . Wtedy funkcja

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

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

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

Obserwacja 2

Dla $0 < k ⩽ n$ mamy:

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

Dowód [Uzupelnij]

Podobnie jak przy budowaniu zależności rekurencyjnej przy zliczaniu wszystkich podzbiorów zbioru $n$ -elementowego załóżmy, że Parser nie mógł rozpoznać (nieznana funkcja „\abs”): {\displaystyle \abs|{Z}|=n} . Wtedy, po usunięciu ze zbioru $Z$ elementu $a \in Z$ dostajemy $(n - 1)$ --elementowy zbiór $Z^{'}$ . Oczywiście wszystkie $k$ -elementowe podzbiory zbioru $Z$ można podzielić na dwa typy:

albo mają w sobie element $a$ ,

albo go nie mają.

W drugim przypadku są to $k$ -elementowe podzbiory $(n - 1)$ --elementowego zbioru $Z^{'}$ . Jest więc ich dokładnie $(\binom{n - 1}{k})$ .

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

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

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

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

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

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

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

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

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

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

Przykład [Uzupelnij]

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

{Rys. 4.1 Szkic na kartce.}

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

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

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

Parser nie mógł rozpoznać (nieznana funkcja „\krot”): {\displaystyle \left \langle \krot{5\choose5},{6\choose5},{7\choose5},{8\choose5},\ldots}\right \rangle =\left \langle \krot{1,6,21,56,\ldots}\right \rangle }

tworzą {przekątną}.

Trójkat Pascala ma zera na obrzeżach, a jego wiersze są symetryczne względem pionowej osi przebiegającej przez środek trójkąta. Jest to konsekwencja Obserwacji {[##obserwacja - podstawowe wlasnosci wspolczynnika|Uzupelnic obserwacja - podstawowe wlasnosci wspolczynnika|]{. Współczynniki dwumianowe spełniają bardzo wiele ciekawych zależności. Wymienimy tylko te najważniejsze. Zaczniemy od wzoru w postaci zwartej.

Obserwacja 3

Dla dowolnych $0 ⩽ k ⩽ n$

(\binom{n}{k}) = \frac{n!}{(n - k)! k!} .

Dowód [Uzupelnij]

Podamy dwa dowody: kombinatoryczny i indukcyjny.

Dowód kombinatoryczny. Ustalmy pewien $n$ -elementowy zbiór $X$ , i wybierajmy po kolei $k$ różnych jego elementów, tzn. utwórzmy injekcję Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle \mathbb{Z}\integer_k \map X} . Z wykładu o zliczaniu zbiorów i funkcji wiemy, ze takich injekcji jest $\frac{n!}{(n - k)!}$ . W wyniku takiego wyboru, dostajemy wszakże pewien uporządkowany ciąg $k$ elementów zbioru $X$ . Wiele takich ciągów wyznacza ten sam $k$ -elementowy podzbiór zbioru $X$ . Ciągi takie różnią sie jedynie kolejnością elementów, a zatem jest ich tyle ile permutacji zbioru $k$ -elemetowego, czyli $k!$ . Zatem jest dokładnie

\frac{n (n - 1) \cdot \dots \cdot (n - k + 1)}{k!} = \frac{n!}{(n - k)! k!}

podzbiorów $k$ -elementowych zbioru $n$ -elementowego.

Dowód indukcyjny. Indukcję poprowadzimy względem górnego indeksu $n$ . Dla $n = 0$ mamy tylko jeden interesujący nas współczynnik $(\binom{0}{0}) = 1$ , i rzeczywiście $\frac{0!}{(0 - 0)! 0!} = 1$ . Załóżmy zatem, że wszystkie współczynniki w $n$ -tym wierszu spełniają wzór z tezy i rozważmy $(\binom{n + 1}{k})$ dla Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle k\in\set\{0,\ldots,n+1\}} . Jeśli $k = 0$ to $(\binom{n + 1}{k}) = 1 = \frac{n!}{(n - 0)! 0!}$ . Załóżmy więc, że $k > 0$ . Wtedy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned{n+1\choose k}&=&{n\choose k-1}+{n\choose k}\\ &=&\frac{n!}{(n-k+1)!(k-1)!}+\frac{n!}{(n-k)!k!}\\ &=&\frac{n!}{(n-k)!(k-1)!}\cdot\left(\frac{1}{n-k+1}+\frac{1}{k}\right)\\ &=&\frac{n!}{(n-k)!(k-1)!}\cdot\frac{k+(n-k+1)}{(n-k+1)k}\\ &=&\frac{(n+1)!}{(n-k+1)!k!}. \endaligned}

Przykład [Uzupelnij]

(\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 [Uzupelnij]

Wyobraźmy sobie, że znajdujemy się w mieście zbudowanym na planie prostopadle przecinających się ulic. Powiedzmy, że znajdujemy się w punkcie $A$ i chcemy dojść do punktu $B$ , tak jak zaznaczono na rysunku.

{4.2 Szkic na kartce.}

Łatwo zauważyć, że jest wiele najkrótszych dróg prowadzących z $A$ do $B$ . Dla przykładu: możemy pójść $3$ razy na północ i potem cały czas na wschód, ale także możemy iść najpierw $6$ razy na na wschód i dopiero wtedy skręcić na północ.

Ile jest najkrótszych dróg z $A$ do $B$ ?

Zauważmy, że każda najkrótsza droga biegnie przez dokładnie $9$ skrzyżowań (licząc skrzyżowanie w punkcie $A$ i nie licząc skrzyżowania w punkcie $B$ ). Na każdym takim skrzyżowaniu musimy podjąć decyzję, czy pójść na wschód czy na północ, przy czym musimy iść dokładnie $3$ razy na północ i dokładnie $6$ razy na wschód.

{4.3 Szkic na kartce.}

Zatem liczba najkrótszych dróg z $A$ do $B$ to liczba wyborów spośród $9$ skrzyżowań, trzech, na których pójdziemy na północ, bądź $6$ na których pójdziemy na wschód. A zatem liczba ta wynosi $(\binom{9}{3}) = (\binom{9}{6}) = 94$ .

W ogólności załóżmy, że mamy kratkę $m \times n$ i chcemy narysować najkrótszą łamaną po krawędziach kratki łączącą lewy dolny wierzchołek z prawym górnym. Na ile sposobów możemy narysować taką łamaną?

Widzimy, że musimy narysować $m + n$ odcinków jednostkowych, z których dokładnie $m$ jest pionowych i dokładnie $n$ jest poziomych. Zatem jest

(\binom{m + n}{m}) = (\binom{m + n}{n}) = \frac{(m + n)!}{m! n!}

sposobów połączenia dwóch przeciwległych wierzchołków.

Przykład [Uzupelnij]

Ile rozwiązań ma równanie

x_{0} + x_{1} + x_{2} + x_{3} + x_{4} = 7,

gdzie $x_{i}$ są liczbami naturalnymi?

Użyjmy kratki rozważanej w poprzednim przykładzie do połączenia przeciwległych jej rogów. W kratce rozmiaru $4 \times 7$ suma poziomych odcinków daje $7$ i jest dokładnie $5$ takich odcinków, po jednym na każdym poziomie. Jeśli długości tych odcinków oznaczymy odpowiednio przez $x_{0}, x_{1}, x_{2}, x_{3}, x_{4}$ , to każda taka droga (łamana) na kratce ustala pewne rozwiązanie naszego równania, i każde rozwiązanie równania wyznacza dokładnie jedna drogę (łamaną). Dla przykładu:

{4.4 Szkic na kartce.}

{4.5 Szkic na kartce.}

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

W ogólności, równanie

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

ma dokładnie tyle rozwiązań w liczbach naturalnych gdzie $x_{i}$ , ile jest łamanych w kratce $k \times n$ , czyli $(\binom{n + k - 1}{n}) = (\binom{n + k - 1}{k - 1})$ .

Przykład [Uzupelnij]

Ile rozwiązań ma równanie

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

gdzie $x_{i}$ są dodatnimi liczbami naturalnymi?

Zauważmy, że każde rozwiązanie tego równania z warunkami $x_{i} ⩾ 1$ , można otrzymać z rozwiązania w liczbach naturalnych równania

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

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

{6.1 Szkic na kartce.}

Separatorem nazywamy pionową kreskę położoną pomiędzy dwoma punktami. Zatem pomiędzy $n$ punktami mamy $n - 1$ możliwych pozycji dla separatora. Zauważmy, że każde rozwiązanie naszego równania jednoznacznie odpowiada jednemu z możliwych rozmieszczeń $k - 1$ separatorów wśród $n - 1$ pozycji. Liczba punktów do pierwszego separatora to wartość $x_{0}$ , liczba punktów pomiędzy pierwszym a drugim separatorem to $x_{1}$ , itd., liczba punktów za ostatnim $k - 1$ -szym separatorem to $x_{k - 1}$ . Dla przykładu:

{6.2 Szkic na kartce.}

Na odwrót każde rozwiązanie $x_{0}, x_{1}, \dots, x_{k - 1}$ naszego równania wyznacza jednoznacznie rozłożenie $k - 1$ separatorów: pierwszy kładziemy po $x_{0}$ punktach, drugi po $x_{0} + x_{1}$ , itd.

Zatem liczba rozwiązań naszego równania to liczba rozmieszczeń $k - 1$ separatorów na $n - 1$ pozycjach, czyli $(\binom{n - 1}{k - 1})$ .

Przykład [Uzupelnij]

Rozważmy znów kratkę, tym razem kwadratową, wielkości $n \times n$ , i policzmy na ile sposobów można w jej wnętrzu narysować prostokąt tak, aby wszystkie jego boki były równoległe do krawędzi kratki?

{Rys. 4.11 Szkic na kartce.}

Zauważmy, że każdy taki prostokąt jest jednoznacznie wyznaczony przez dwie linie poziome (spośród $n + 1$ ) oraz dwie linie pionowe (znów spośród $n + 1$ ). Rzeczywiście, dowolny prostokąt wyznacza dwie linie poziome i dwie pionowe (te przylegające do jego boków). I na odwrót dowolny wybór linii pozwoli nam nakreślić jednoznacznie prostokąt w kratce.

Poziome linie możemy wybrać na $(\binom{n + 1}{2})$ sposobów i pionowe linie także na $(\binom{n + 1}{2})$ sposobów. Zatem prostokąt w kratce $n \times n$ możemy narysować na dokładnie

{(\binom{n + 1}{2})}^{2} = {(\frac{n (n + 1)}{2})}^{2}

sposobów. W przykładowej kratce na rysunku wymiarów $5 \times 5$ możemy więc umieścić ${(\frac{5 (5 + 1)}{2})}^{2} = 225$ prostokątów.

Przechodzimy teraz do kolejnych własności współczynników dwumianowych. Rozpoczniemy od sumowania liczb na przekątnej trójkąta Pascala. Przekątna taka jest oczywiście nieskończona -- sumujemy więc tylko jej początkowy fragment.

Obserwacja 4 (reguła sumowania po górnym indeksie)

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

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

{4.6 Szkic na kartce.}

Dowód [Uzupelnij]

Ustalmy $(n + 1)$ -elementowy zbiór Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle X=\set\{x_0,\ldots,x_n\}} Rozważając jego $(k + 1)$ -elementowe podzbiory zwracamy uwagę na element tego podzbioru, który ma największy indeks. Oczywiście jest $i ⩾ k$ , gdyż Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle X=\set\{x_0,\ldots,x_{k-1}\}} nie ma $(k + 1)$ -elementowych podzbiorów. Równie łatwo jest zauważyć, że jest dokładnie jeden podzbiór $(k + 1)$ -elementowy w którym $x_{k}$ jest elementem o najwyższym indeksie, jest to zbiór Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{x_0,\ldots,x_{k-1}\}} .

Policzmy teraz podzbiory zbioru $X$ , w których $x_{i}$ jest elementem o największym indeksie, przy czym $i > k$ . Oprócz elementu $x_{i}$ każdy taki zbiór ma dokładnie $k$ elementów wybranych z $i$ -elementowego zbioru Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \set\{x_0,\ldots,x_{i-1}\}} . Wyboru tych elementów można dokonać na $(\binom{i}{k})$ sposobów. Zatem podzbiorów zbioru $X$ , w których $x_{i}$ jest elementem o największym indeksie jest dokładnie $(\binom{i}{k})$ . Sumując po wszystkich możliwych $i$ , czyli Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle i\in\set\{k,\ldots,n\}} otrzymujemy:

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

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

Obserwacja 5

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

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

{4.7 Szkic na kartce.}

Dowód [Uzupelnij]

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

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

Obserwacja 6

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

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

Dowód [Uzupelnij]

Policzymy liczbę wszystkich wyborów $k$ osób z grona $m$ mężczyzn i $n$ kobiet, czyli liczbę $(\binom{m + n}{k})$ na jeszcze jeden sposób. Wybierając $k$ osób wybieramy najpierw $i$ mężczyzn na $(\binom{m}{i})$ sposobów, a potem $k - i$ kobiet na $(\binom{n}{k - i})$ sposobów. Pozostaje teraz zsumować po wszystkich możliwych wartościach parametru $i$ .

Dwumiany

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

Obserwacja 7

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

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

Dowód [Uzupelnij]

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

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

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

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

Przykład [Uzupelnij]

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

Wniosek 8

Dla dowolnego

n ⩾ 0

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

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

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

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

{4.8 Szkic na kartce.}

Dowód [Uzupelnij]

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

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

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

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

liczbie podzbiorów $X$ o nieparzystej liczbie elementów.

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

Załóżmy zatem, że $n$ jest parzyste i ustalmy $x \in X$ . Zdefiniujmy funkcję Parser nie mógł rozpoznać (nieznana funkcja „\map”): {\displaystyle f:\mathcal{P}(X)\map\mathcal{P}(X)} , kładąc

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

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

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

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

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

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

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

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

Uogólniony współczynnik dwumianowy

Wniosek {[##wniosek - suma i naprzemienna suma wiersza|Uzupelnic wniosek - suma i naprzemienna suma wiersza|]} pozwala na ustalenie wartość sumy całego wiersza w Trójkącie Pascala i wartość naprzemiennej sumy całego wiersza Trójkąta Pascala. W praktyce często pojawia się konieczność (naprzemiennego) sumowania tylko pewnego fragmentu takiego wiersza. Do tego pomocne mogłyby być sumy postaci:

\begin{array}{lclc} \sum_{i = 0}^{m} (\binom{n}{i}) & = & (\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{m}) & (*) \\ \sum_{i = 0}^{m} (- 1)^{i} (\binom{n}{i}) & = & (\binom{n}{0}) - (\binom{n}{1}) + \dots + (- 1)^{m} (\binom{n}{m}) & (* *) \end{array}

dla $0 ⩽ m < n$ .

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

Obserwacja 9

Dla

m, n ⩾ 0

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

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

{Uogólniony współczynnik dwumianowy} $(\binom{r}{k})$ dla $r \in ℝ$ i $k \in ℤ$ to:

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

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

Obserwacja 10

Dla

r \in ℝ ℜ

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

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

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

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

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

Przykład [Uzupelnij]

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

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

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

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

Zachowana jest natomiast {reguła dodawania}.

Obserwacja 11

Dla

r \in ℝ ℜ

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

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

Dowód [Uzupelnij]

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

(\binom{r}{k}) - (\binom{r - 1}{k}) - (\binom{r - 1}{k - 1})

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

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

{Rys. 4.9 Szkic na kartce.}

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

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

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

Obserwacja 12

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

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

Dowód [Uzupelnij]

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned(-1)^k r^{\underline{k}} &=&(-1)^k r(r-1)\cdot\ldots\cdot(r-k+1)\\ &=&(-r)(1-r)\cdot\ldots\cdot(k-1-r)\\ &=&(k-r-1)^{\underline{k}}. \endaligned}

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

Obserwacja 13

Dla

r \in ℝ ℜ

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

\sum_{i ⩽ k} (\binom{r + i}{i}) = (\binom{r + k + 1}{k}) .

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

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

Obserwacja 14

Dla

r \in ℝ ℜ

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

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

Dowód [Uzupelnij]

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

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

Obserwacja 15

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

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

Dowód [Uzupelnij]

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned{r\choose i}{i\choose j}&=&\frac{r^{\underline{i}}}{i!}\cdot\frac{i^{\underline{j}}}{j!}\\ &=&\frac{r(r-1\cdot\ldots\cdot(r-i+1))}{i!}\cdot\frac{i(i-1)\cdot\ldots\cdot(i-j+1)}{j!}\\ &=&\frac{r(r-1)\cdot\ldots\cdot(r-j+1)}{j!}\cdot\frac{(r-j)(r-j-1)\cdot\ldots\cdot(r-i+1)}{(i-j)!}\\ &=&{r\choose j}{r-j\choose i-j}. \endaligned}

Obserwacja 16

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

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

wtedy i tylko wtedy, gdy

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

Dowód [Uzupelnij]

Uzupelnic wniosek - suma i naprzemienna suma wiersza

Permutacje bez punktów stałych

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

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

Przykład [Uzupelnij]

Zbiór Parser nie mógł rozpoznać (nieznana funkcja „\integer”): {\displaystyle \mathbb{Z}\integer_4=\set\{0,1,2,3\}} ma $4! = 24$ permutacje, ale tylko $9$ z nich to nieporządki. Oto ich lista:

\begin{array}{cccccccccccccc} 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 \\ ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ \\ 1 & 0 & 3 & 2 & 1 & 2 & 3 & 0 & 1 & 3 & 0 & 2 \\ 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 \\ ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ \\ 2 & 0 & 3 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 1 & 0 \\ 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 \\ ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ \\ 3 & 0 & 1 & 2 & 3 & 2 & 0 & 1 & 3 & 2 & 1 & 0 \end{array}

Obserwacja 17

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

Dowód [Uzupelnij]

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

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

Aplikując teraz regułę odwracania dostajemy:

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

Współczynniki multimianowe

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

{Współczynnik multimianowy} $(\binom{n}{k_{1}, k_{2} \dots, k_{r}})$ , dla Parser nie mógł rozpoznać (nieznana funkcja „\natur”): {\displaystyle n\in\mathbb{Z}\natur} , $r ⩾ 2$ oraz całkowitych $k_{1}, \dots, k_{r}$ takich, że $k_{1} + \dots k_{r} = n$ , to liczba sposobów umieszczenia $n$ obiektów w $r$ pudełkach z odpowiednio $k_{1}$ obiektami w pierwszym pudełku, $k_{2}$ w drugim, itd., oraz $k_{r}$ w $r$ -tym. Jeśli którakolwiek z liczb $k_{i}$ jest ujemna to współczynnik jest równy $0$ . Zauważmy, że z uwagi na symetrię dolnych indeksów, ich kolejność nie jest istotna. Oczywiście $(\binom{n}{k})$ to w nowej notacji $(\binom{n}{k, n - k})$ .

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

Obserwacja 18

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

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

zachodzi:

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

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

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

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

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

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

Następna obserwacja wymaga krótkiego uzasadnienia.

Obserwacja 19

Dla

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

takich, że

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

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

Dowód [Uzupelnij]

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

wyborze $k_{1}$ obiektów spośród wszystkich $n$

i umieszczeniu ich w pierwszym pudełku -- możemy to uczynić na $(\binom{n}{k_{1}})$ sposobów,

wyborze $k_{2}$ obiektów spośród pozostałych $n - k_{1}$

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

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

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

...

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

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

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

Obserwacja 20

Dla

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

takich, że

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

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

Dowód [Uzupelnij]

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned{n\choose k_1,\ldots,k_r} &=&{n\choose k_1}{n-k_1\choose k_2}{n-(k_1+k_2)\choose k_3}\cdot\ldots\cdot{n-(k_1+\ldots+k_{r-1})\choose k_r}\\ &=&\frac{n!}{(n-k_1)!k_1!}\cdot\frac{(n-k_1)!}{(n-(k_1+k_2))!k_2!} \cdot\ldots\cdot\frac{(n-(k_1+\ldots+k_{r-1}))!}{(n-(k_1+\ldots+k_r))!k_r!}\\ &=&\frac{n!}{k_1!\cdot\ldots\cdot k_r!\cdot(n-(k_1+\ldots+k_r))!}\\ &=&\frac{n!}{k_1!\cdot\ldots\cdot k_r!}. \endaligned}

Przykład [Uzupelnij]

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

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

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

Przykład [Uzupelnij]

Rozważmy raz jeszcze podróż w mieście o ulicach na planie siatki. Tym razem jednak... $3$ -wymiarową wersję. Mamy więc do dyspozycji trójwymiarową, prostopadłościenną kratownicę $a \times b \times c$ . Na ile sposobów można połączyć przeciwległe wierzchołki prostopadłoscianu najkrótszą możliwą łamaną

Zauważmy, że każda najkrótsza możliwa łamana składa się z dokładnie $a + b + c$ odcinków jednostkowych. Przy czym dokładnie $a$ z nich jest poziomych, $b$ pionowych i $c$ idzie w głąb. Zatem najkrótszych łamanych jest tyle co rozmieszczeń $a + b + c$ odcinków (obiekty) w $3$ pudełkach: "poziomy", "pionowy", "w głąb" tak, by w było ich odpowiednio $a, b$ i $c$ . Z definicji współczynnika multimianowego mamy zatem:

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

łamanych.

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

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

Obserwacja 21

Dla

n > 0

, całkowitych

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

takich, że

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

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

Dowód [Uzupelnij]

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

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

Obserwacja 22

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

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

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