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

Wersja z 22:26, 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}}

@@ Linia 17: / Linia 17: @@
 {{obserwacja|5.1|obs 5.1|
-Dla <math>n,k \in  \mathbb{R}</math> zachodzi:
+Dla <math>n,k \in \mathbb{R}</math> zachodzi:
 * <math>{n\choose 0}={n\choose n}=1</math>,
@@ Linia 53: / Linia 53: @@
-<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>

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

Wersja z 22:26, 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