--- title: "Kombinatoryka" lecture_number: 7 has_solutions: true has_exercises: true file_format: mystnb kernelspec: name: sagemath display_name: SageMath --- ```{include} ../_includes/sagecell-loader.md ``` # Kombinatoryka ## Permutacje :::{narration} Niech $X, Y$ będą zbiorami skończonymi. ::: :::{prf:definition} Funkcja $f : X\to Y$ jest {index}`bijekcja` **bijekcją**, jeśli jest: - **injekcją** (funkcją **różnowartościową**), czyli ```{math} \forall x_1,x_2\in X \; (x_1\neq x_2\;\imply\; f(x_1)\neq f(x_2)) ``` - **surjekcją** (funkcją **"na"**), czyli ```{math} \forall y\in Y \; \exists x\in X\; y=f(x). ``` ::: :::{prf:definition} **Permutacją** {index}`permutacja` zbioru $X$ nazywamy dowolną bijekcję ```{math} \pi : X \to X. ``` Permutację zbioru $X=\{a_1,\ldots,a_n\}$ zapisujemy w postaci tablicy ```{math} \pi = \begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ \pi(a_1) & \pi(a_2) & \cdots & \pi(a_n) \end{pmatrix}. ``` Zbiór wszystkich permutacji zbioru $X$ oznaczamy $S_X$, a w przypadku $X=\{1,\ldots,n\}$ -- symbolem $S_n .$ ::: :::{prf:proposition} Liczba wszystkich permutacji $n$-elementowego zbioru $X$ wynosi $|S_X| = n! .$ ::: :::{prf:example} 1. Na każdym zbiorze skończonym $X$ istnieje permutacja identycznościowa: $$ \id_X : X \to X, \quad \id_X(x) = x. $$ 2. Zbiór $S_2$ składa się z dwóch permutacji: $$ \begin{aligned} \id_2 = \left(\begin{array}{cc} 1 & 2\\ 1 & 2 \end{array}\right), \quad \left(\begin{array}{cc} 1 & 2\\ 2 & 1 \end{array}\right). \end{aligned} $$ 3. Zbiór $S_3$ składa się z $3!=6$ permutacji: $$ \begin{aligned} \id_3 = \left(\begin{array}{ccc} 1 & 2 & 3 \\ 1&2 & 3 \end{array}\right), && \left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3&1 \end{array}\right), && \left(\begin{array}{ccc} 1 & 2 & 3 \\ 3&1&2 \end{array}\right), \\ \left(\begin{array}{ccc} 1 & 2 & 3 \\ 1&3 & 2 \end{array}\right), && \left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 2&1 \end{array}\right), && \left(\begin{array}{ccc} 1 & 2 & 3 \\ 2&1&3 \end{array}\right). \end{aligned} $$ które odpowiadają różnym sposobom ustawienia w kolejności elementów zbioru $\{1,2,3\}$: $$ 123,\quad 231,\quad 312,\quad 132,\quad 321,\quad 213. $$ ::: ### Grupa permutacji :::{narration} Ponieważ permutacje $\pi, \sigma \in S_X$ są funkcjami $\pi, \sigma : X \to X$ o tej samej dziedzinie i przeciwdziedzinie, możemy je -- tak jak dowolne funkcje -- składać ze sobą, a skoro są bijekcjami, możemy też mówić o funkcji do nich odwrotnej. ::: :::{prf:definition} **Złożeniem** {index}`permutacja; złożenie` permutacji $\pi, \sigma \in S_X$ nazywamy permutację $\pi\circ\sigma \in S_X$ zadaną wzorem ```{math} (\pi\circ\sigma)(x) = \pi(\sigma(x)), \qquad x \in X. ``` W złożeniu $\pi \circ \sigma$ najpierw działamy permutacją $\sigma$, a dopiero na otrzymanym wyniku permutacją $\pi .$ ::: :::{prf:remark} Zapisując $\pi, \sigma$ w postaci tablic, złożenie $\pi \circ \sigma$ obliczamy, podstawiając kolejno wartości z dolnego wiersza tablicy $\sigma$ jako argumenty do $\pi$: ```{math} \sigma = \begin{pmatrix} x_1 & x_2 & \cdots & x_n \\ \sigma(x_1) & \sigma(x_2) & \cdots & \sigma(x_n)\end{pmatrix} \qquad \imply \qquad \pi\circ\sigma = \begin{pmatrix} x_1 & x_2 & \cdots & x_n \\ \pi(\sigma(x_1)) & \pi(\sigma(x_2)) & \cdots & \pi(\sigma(x_n))\end{pmatrix}. ``` ::: :::{prf:definition} **Permutacją odwrotną** {index}`permutacja; odwrotna` do permutacji $\pi \in S_X$ nazywamy funkcję odwrotną $\pi^{-1} \in S_X$, czyli permutację spełniającą ```{math} \pi^{-1}\circ\pi = \pi\circ\pi^{-1} = \id_X. ``` Ponieważ $\pi$ jest bijekcją, permutacja odwrotna $\pi^{-1}$ zawsze istnieje i jest wyznaczona jednoznacznie. ::: :::{prf:remark} Permutację odwrotną $\pi^{-1}$ zapisujemy w postaci tablicy, zamieniając miejscami oba wiersze tablicy $\pi$ (a następnie, dla czytelności, porządkując kolumny według rosnących wartości górnego wiersza): ```{math} \pi = \begin{pmatrix} x_1 & \cdots & x_n \\ \pi(x_1) & \cdots & \pi(x_n)\end{pmatrix} \qquad \imply \qquad \pi^{-1} = \begin{pmatrix} \pi(x_1) & \cdots & \pi(x_n) \\ x_1 & \cdots & x_n\end{pmatrix}. ``` ::: :::{prf:example} Dla ```{math} \pi=\begin{pmatrix}1&2&3&4\\2&3&4&1\end{pmatrix},\qquad \sigma=\begin{pmatrix}1&2&3&4\\4&3&2&1\end{pmatrix} ``` mamy ```{math} \pi\circ\sigma=\begin{pmatrix}1&2&3&4\\4&3&2&1\\1&4&3&2\end{pmatrix},\qquad \sigma\circ\pi=\begin{pmatrix}1&2&3&4\\2&3&4&1\\3&2&1&4\end{pmatrix}, ``` czyli $\pi\circ\sigma\neq\sigma\circ\pi .$ Ponadto ```{math} \pi^{-1}=\begin{pmatrix}2&3&4&1\\1&2&3&4\end{pmatrix}=\begin{pmatrix}1&2&3&4\\4&1&2&3\end{pmatrix}. ``` ::: :::{prf:remark} Zbiór $S_X$ z działaniem składania $\circ$, tworzy grupę: - składanie jest łączne: $\quad \Forall{\pi,\sigma,\tau \in S_X} \Paren{\pi \circ \sigma}\circ \tau = \pi \circ \Paren{\sigma \circ \tau}$ - elementem neutralnym jest identyczność $\id_X$: $\quad \Forall{\pi \in S_X} \id_X \circ \pi = \pi \circ \id_X = \pi$ - dla każdej permutacji $\pi$ istnieje permutacja odwrotna $\pi^{-1} .$ Składanie permutacji nie jest na ogół przemienne, co widzieliśmy w poprzednim przykładzie. ::: ### Rozkład na cykle :::{prf:definition} **Cyklem** {index}`cykl` długości $k$ nazywamy permutację $\pi\colon X\to X$, oznaczaną $(a_1\,a_2\,\ldots\,a_k)$, taką że ```{math} \pi(a_i) & = a_{i+1} \quad \text{ dla } i\in\{1,\ldots,k-1\}, \\ \pi(a_k) & = a_1, \\ \pi(a) & = a \quad \text{ dla } a\in X\setminus\{a_1,\ldots,a_k\}. \\ ``` Cykl długości $2$ nazywamy **transpozycją** {index}`transpozycja`. Cykle $(a_1\,\ldots\,a_k)$ i $(b_1\,\ldots\,b_l)$ nazywamy **rozłącznymi** {index}`cykl; rozłączny`, jeśli $\{a_1,\ldots,a_k\}\cap\{b_1,\ldots,b_l\}=\emptyset .$ ::: :::{prf:example} Cykl $(2\,7\,1\,5)$ długości $4$ w $S_9$, czyli permutacja przekształcająca $2\mapsto 7\mapsto 1\mapsto 5\mapsto 2$ i ustalająca pozostałe elementy zbioru $\{1,\ldots,9\}$, ma postać tablicy ```{math} (2\,7\,1\,5) = \begin{pmatrix}1&2&3&4&5&6&7&8&9\\5&7&3&4&2&6&1&8&9\end{pmatrix} \in S_9. ``` ::: :::{prf:definition} Dla permutacji $\pi\colon X\to X$ i $a\in X$, **orbitą** {index}`orbita` elementu $a$ ze względu na $\pi$ nazywamy zbiór ```{math} O(a) := \Set{\pi^k(a) : k\in\nn}. ``` Elementy jednej orbity tworzą pewien cykl permutacji $\pi .$ ::: :::{prf:example} 1. Dla cyklu $(2\,7\,1\,5)\in S_9$ z powyższego przykładu mamy ```{math} O(2)=O(7)=O(1)=O(5)=\{1,2,5,7\}, ``` natomiast pozostałe elementy $3,4,6,8,9$ są punktami stałymi $\pi$, więc tworzą jednoelementowe orbity $$ O(a)=\{a\} \quad \text{ dla } a \in \Set{3,4,6,8,9}. $$ Ogólnie, wszystkie elementy jednego cyklu mają zawsze tę samą orbitę. 2. Dla ```{math} \pi=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&6&8&1&9&2&5&4&7\end{pmatrix} ``` mamy $\pi(1)=3,\ \pi^2(1)=8,\ \pi^3(1)=4,\ \pi^4(1)=1$, więc $$ O(1)=\{1,3,4,8\} \quad \text{ odpowiada cyklowi } (1\,3\,8\,4). $$ Podobnie $\quad O(2)=\{2,6\} \quad$ daje cykl $(2\,6)$, zaś $\quad O(5)=\{5,9,7\} \quad$ daje cykl $(5\,9\,7) .$ ::: :::{prf:theorem} Każdą permutację można przedstawić w postaci złożenia parami rozłącznych cykli. Rozkład ten jest jednoznaczny z dokładnością do kolejności czynników. ::: :::{prf:example} Permutacja $\pi$ z poprzedniego przykładu rozkłada się jako ```{math} \pi = (1\,3\,8\,4)\circ(2\,6)\circ(5\,9\,7). ``` ::: :::{prf:theorem} Każdy cykl długości $k$ jest złożeniem $k-1$ transpozycji (niekoniecznie rozłącznych): ```{math} (a_1\,a_2\,\ldots\,a_k) = (a_1\,a_k)\circ(a_1\,a_{k-1})\circ\cdots\circ(a_1\,a_2). ``` W szczególności każda permutacja jest złożeniem transpozycji. ::: :::{prf:example} Dla przykładu: ```{math} (1\,3\,8\,4) = (1\,4)\circ(1\,8)\circ(1\,3), \qquad (5\,9\,7)=(5\,7)\circ(5\,9), ``` więc permutacja $\pi$ z poprzednich przykładów rozkłada się jako ```{math} \pi = (1\,4)\circ(1\,8)\circ(1\,3)\circ(2\,6)\circ(5\,7)\circ(5\,9), ``` czyli jest złożeniem $6$ transpozycji. ::: ### Znak i parzystość :::{prf:theorem} Jeśli $$ \pi=\tau_1\circ\cdots\circ\tau_r = \tau_1'\circ\cdots\circ\tau_s', $$ gdzie wszystkie $\tau_i,\tau_j'\in S_X$ są transpozycjami, to $$ (-1)^r=(-1)^s. $$ Innymi słowy, parzystość liczby transpozycji w rozkładzie permutacji $\pi$ nie zależy od wyboru rozkładu. ::: :::{prf:definition} Liczbę $(-1)^r$, gdzie $\pi$ jest złożeniem $r$ transpozycji, nazywamy **znakiem** {index}`permutacja; znak` permutacji $\pi$ i oznaczamy $\sgn\pi .$ Permutację $\pi$ nazywamy: - **parzystą**, {index}`permutacja; parzysta` gdy $\sgn\pi=1$ - zaś **nieparzystą**, {index}`permutacja; nieparzysta` gdy $\sgn\pi=-1 .$ ::: :::{prf:example} Dla $$ \pi=(1\,4)\circ(1\,8)\circ(1\,3)\circ(2\,6)\circ(5\,7)\circ(5\,9) $$ mamy $\sgn\pi=(-1)^6=1$, więc $\pi$ jest permutacją parzystą. ::: :::{prf:remark} 1. Identyczność jest permutacją parzystą. 2. Złożenie dwóch permutacji parzystych jest permutacją parzystą; złożenie permutacji parzystej i nieparzystej jest nieparzyste. 3. Permutacja odwrotna do parzystej jest parzysta. 4. Cykl długości $k$ jest permutacją parzystą, gdy $k$ jest liczbą nieparzystą, oraz permutacją nieparzystą, gdy $k$ jest liczbą parzystą. 5. Dla $n\geq 2$, zbiór $A_n\subseteq S_n$ wszystkich permutacji parzystych ma $|A_n|=\dfrac{n!}{2}$ elementów. 6. Parzystość permutacji $\pi\in S_n$ można też odczytać z liczby **inwersji** {index}`inwersja` -- par $(\pi(i),\pi(j))$ takich, że $i\pi(j) .$ Permutacja $\pi$ jest parzysta wtedy i tylko wtedy, gdy liczba jej inwersji jest parzysta. Na przykład dla $$ \pi = \begin{pmatrix}1&2&3&4&5\\3&5&2&1&4\end{pmatrix} $$ inwersjami są pary $(3,2),\ (3,1),\ (5,2),\ (5,1),\ (5,4),\ (2,1)$, czyli jest ich $6$, więc $\pi$ jest parzysta. ::: ## Wariacje i kombinacje :::{narration} Niech $S$ będzie zbiorem $n$-elementowym i niech $r\in\nn_0 .$ ::: :::{prf:definition} 1. **Permutacją** {index}`permutacja` zbioru $S$ nazywamy uporządkowany ciąg wszystkich elementów zbioru $S .$ 2. **Wariacją bez powtórzeń** {index}`wariacja; bez powtórzeń` długości $r$ lub **$r$-permutacją** ze zbioru $S$ ($0 \le r \le n$) nazywamy uporządkowany ciąg $r$ **różnych** elementów ze zbioru $S .$3 4. **Wariacją (z powtórzeniami)** {index}`wariacja; z powtórzeniami` długości $r$ ze zbioru $S$ nazywamy dowolny uporządkowany ciąg $r$ elementów zbioru $S$, przy czym elementy **mogą się powtarzać**. 4. **$r$-kombinacją** {index}`kombinacja` zbioru $S$ ($0 \le r \le n$) nazywamy nieuporządkowany wybór $r$ elementów ze zbioru $S$ (czyli po prostu $r$-elementowy podzbiór zbioru $S$). ::: :::{prf:example} Dla zbioru $S = \{1, 2, 3\}$: - Ciąg $(3, 1, 2)$ jest permutacją zbioru $S .$ - Ciąg $(1,3)$ jest $2$-permutacją, czyli wariacją bez powtórzeń, podobnie jak $(3,1)$ -- to dwie **różne** wariacje, gdyż kolejność ma znaczenie. Są to zarazem wariacje z powtórzeniami. - Ciąg $(2,2)$ jest wariacją z powtórzeniami, ale nie jest wariacją bez powtórzeń, gdyż element $2$ powtarza się. - Zbiór $\{1, 3\}$ jest $2$-kombinacją zbioru $S$ (zauważmy, że $\{3, 1\}$ to ta sama $2$-kombinacja). ::: :::{prf:proposition} Liczbę wariacji bez powtórzeń długości $r$ ze zbioru $n$-elementowego oznaczamy przez $P(n,r)$ i dla $0\leq r\leq n$ wyraża się ona wzorem ```{math} P(n,r) = n(n-1)(n-2)\cdots (n-r+1) = \frac{n!}{(n-r)!}. ``` Liczbę wariacji z powtórzeniami długości $r$ ze zbioru $n$-elementowego oznaczamy przez $V(n,r)$ i dla dowolnego $r\in \nn_0$ wyraża się ona wzorem ```{math} V(n,r) = n^r. ``` ::: :::{prf:remark} Ponieważ permutacje zbioru $n$-elementowego, to oczywiście jego $n$-permutacje, więc liczba permutacji jest równa $$ P(n,n) = \frac {n!} {0!} = n!\, . $$ ::: ::::{exercise} :class: [exercise] Ile jest możliwych czteroliterowych "słów" (bez wymogu sensowności) utworzonych z liter $\Set{A,B,C,D,E}$, jeśli: :::{container} columns-2-auto 1. litery nie mogą się powtarzać, 2. litery mogą się powtarzać? ::: :::: :::{solution-without-reference} :class: [solution] dropdown Mamy zbiór $5$-elementowy, z którego wybieramy uporządkowane ciągi długości $4 .$ 1. Litery bez powtórzeń -- liczba wariacji bez powtórzeń: ```{math} P(5,4) = 5\cdot 4\cdot 3\cdot 2 = 120. ``` 2. Litery z powtórzeniami -- liczba wariacji z powtórzeniami: ```{math} V(5,4) = 5^4 = 625. ``` ::: ::::{exercise} :class: [exercise] Rejestracja tablic w pewnym systemie składa się z $3$ cyfr (od $0$ do $9$), przy czym cyfry mogą się powtarzać. Ile różnych tablic można utworzyć, a ile z nich ma wszystkie cyfry różne? :::: :::{solution-without-reference} :class: [solution] dropdown Zbiór cyfr $\Set{0,1,\ldots,9}$ ma $n=10$ elementów, a długość ciągu to $r=3 .$ - Wszystkich tablic (cyfry mogą się powtarzać): ```{math} V(10,3) = 10^3 = 1000. ``` - Tablic o wszystkich cyfrach różnych: ```{math} P(10,3) = 10\cdot 9\cdot 8 = 720. ``` ::: :::{prf:proposition} Liczbę $r$-kombinacji zbioru $n$-elementowego oznaczamy przez $C(n, r)$ lub $\binom{n}{r}$ i dla $0 \le r \le n$ wyraża się ona wzorem: ```{math} C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}. ``` ::: :::{prf:remark} Między liczbą $r$-kombinacji a liczbą wariacji bez powtórzeń zachodzi prosty związek: ```{math} P(n,r) = C(n,r)\cdot P(r,r) , \qquad \text{czyli} \qquad C(n,r) = \frac{P(n,r)}{P(r,r)}. ``` Wynika to stąd, że każdą wariację bez powtórzeń długości $r$ można otrzymać w dwóch krokach: 1. wybieramy $r$-elementowy podzbiór zbioru $S$ (czyli $r$-kombinację) -- na $C(n,r)$ sposobów, 2. ustawiamy wybrane $r$ elementów w dowolnej kolejności, czyli wybieramy ich permutację -- na $P(r,r)$ sposobów. Ponieważ te dwa kroki są od siebie niezależne, liczba wszystkich wariacji bez powtórzeń jest iloczynem liczby sposobów wykonania obu kroków. Innymi słowy: **kombinacja to "zapomniana kolejność" wariacji bez powtórzeń** -- każdej $r$-kombinacji odpowiada dokładnie $r!$ różnych wariacji bez powtórzeń (tych samych elementów, w różnej kolejności). ::: :::{exercise} :class: [exercise] Na ile sposobów można wybrać $6$-osobową załogę do misji kosmicznej spośród $30$ wyszkolonych kandydatów? ::: :::{solution-without-reference} :class: [solution] dropdown Rola każdego członka załogi jest taka sama, więc kolejność wyboru nie ma znaczenia. Liczba sposobów to liczba $6$-kombinacji zbioru $30$-elementowego: ```{math} \binom{30}{6} = \frac{30!}{6! \cdot 24!} = \frac{30 \cdot 29 \cdot 28 \cdot 27 \cdot 26 \cdot 25}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 593\,775. ``` ::: ## Współczynniki dwumianowe i trójkąt Pascala :::{prf:definition} Dla $0\leq k\leq n$, liczbę ```{math} \binom{n}{k} = \frac{n!}{k!(n-k)!} ``` nazywamy **współczynnikiem dwumianowym** {index}`współczynnik dwumianowy` (czytamy: "$n$ nad $k$"). Zgodnie z poprzednim paragrafem, $\binom{n}{k}$ jest liczbą $k$-elementowych podzbiorów zbioru $n$-elementowego. ::: :::{prf:remark} Dla dowolnego $n\in n$ oraz $0\leq k\leq n$: 1. $\binom{n}{0}=\binom{n}{n}=1$ 2. $\binom{n}{1}=\binom{n}{n-1}=n$ 3. $\binom{n}{k}=\binom{n}{n-k}$ 4. $\binom{n}{2}=\dfrac{n(n-1)}{2}=1+2+\cdots+(n-1)$ ::: :::{prf:proposition} Wzór Pascala :label: thm-pascal Dla $0\leq k\leq n$ zachodzi ```{math} \binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}. ``` ::: :::{proof} Dowód kombinatoryczny :class: [proof] dropdown Chcemy wybrać **$(k+1)$-elementowy podzbiór** ze zbioru $S$, który ma **$n+1$ elementów**. Liczba wszystkich takich wyborów z definicji wynosi **$\binom{n+1}{k+1}$**. Wybierzmy jeden dowolny, wyróżniony element ze zbioru $S$ i nazwijmy go $x .$ Wszystkie możliwe $(k+1)$-elementowe podzbiory możemy podzielić na dwie rozłączne grupy: - **Podzbiory zawierające element $x$:** Skoro element $x$ już znajduje się w naszym podzbiorze, musimy dobrać do niego pozostałe $k$ elementów z reszty zbioru (czyli z pozostałych $n$ elementów). Możemy to zrobić na **$\binom{n}{k}$** sposobów. - **Podzbiory niezawierające elementu $x$:** Skoro nie wybieramy elementu $x$, musimy wybrać wszystkie $k+1$ elementów wyłącznie z pozostałych $n$ elementów. Możemy to zrobić na **$\binom{n}{k+1}$** sposobów. Z uwagi na to, że każdy podzbiór albo zawiera $x$, albo go nie zawiera (przypadki są rozłączne i wyczerpują wszystkie możliwości), suma obu przypadków daje całkowitą liczbę podzbiorów: $$\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}$$ ::: :::{prf:remark} Wzór Pascala pozwala obliczać kolejne współczynniki dwumianowe rekurencyjnie i ustawić je w **trójkąt Pascala** {index}`trójkąt Pascala`, w którym każdy wpis (poza brzegowymi jedynkami) jest sumą dwóch wpisów bezpośrednio nad nim: $$ \begin{aligned} \begin{array}{rcccccccccccccc} n=0&&&& & & &{0\choose 0} & & & & &&&\\ n=1&&&& & &{1\choose 0} & & {1\choose 1}& & & &&&\\ n=2&&&& & {2\choose 0} & & {2\choose 1}& &{2\choose 2} & &&&&\\ n=3&&&&{3\choose 0} & & {3\choose 1} & & {3\choose 2}& & {3\choose 3}&&&&\\ n=4&&&{4\choose 0}& & {4\choose 1} & &{4\choose 2} & & {4\choose 3}& & {4\choose 4}&&&\\ n=5&&{5\choose 0}&& {5\choose 1}& & {5\choose 2} & &{5\choose 3} & &{5\choose 4} &&{5\choose 5}&&\\ n=6&{6\choose 0}&&{6\choose 1}& & {6\choose 2} & & {6\choose 3}& &{6\choose 4} & &{6\choose 5}&&{6\choose 6}& \end{array} \end{aligned} $$ ::: :::{prf:proposition} Wzór dwumianowy Newtona Dla dowolnych liczb $a,b$ oraz $n\in n$: ```{math} (a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k. ``` ::: :::{prf:remark} Wstawiając we wzorze Newtona $a=b=1$ otrzymujemy $$ 2^n = \sum_{k=0}^{n}\binom{n}{k}. $$ To oznacza, że suma współczynników w $n+1$-szym wierszu trójkąta Pascala jest równa właśnie $2^n .$ $$ \begin{aligned} \begin{array}{rcccccccccccccc} 2^0=1&&&& & & &1 & & & & &&&\\ 2^1=2&&&& & &1 & & 1& & & &&&\\ 2^2=4&&&& & 1 & & 2& &1 & &&&&\\ 2^3=8&&&&1 & & 3 & & 3& & 1&&&&\\ 2^4=16&&&1& & 4 & &6 & & 4& & 1&&&\\ 2^5=32&&1&& 5& & 10 & &10 & &5 &&1&&\\ 2^6=64&1&&6& & 15 & & 20& &15 & &6&&1& \end{array} \end{aligned} $$ Zauważmy, że jest to jednocześnie liczba wszystkich podzbiorów zbioru $n$-elementowego, czyli $|2^X| = 2^n$ dla $|X|=n .$ ::: ## Tożsamości kombinatoryczne ::::{prf:theorem} Dla dowolnego $n\in\nn$: :::{container} columns-2-auto 1. $\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n$ 2. $\displaystyle\sum_{k=1}^{n}k\binom{n}{k}=n\cdot 2^{n-1}$ 3. $\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0 \quad \text{dla } n \ge 1$ 4. $\displaystyle\sum_{k=0}^{n}2^k\binom{n}{k}=3^n$ 5. $\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2=\binom{2n}{n} .$ ::: :::: :::{proof} Dwa dowody tożsamości 2. :class: [proof] dropdown **Dowód kombinatoryczny tożsamości 2.** Policzmy na dwa sposoby, na ile sposobów można wybrać spośród $n$ osób niepustą komisję wraz z jej przewodniczącym. - *Sposób I.* Najpierw wybieramy przewodniczącego -- na $n$ sposobów -- a następnie dowolny podzbiór pozostałych $n-1$ osób jako resztę komisji -- na $2^{n-1}$ sposobów. Razem: $n\cdot 2^{n-1} .$ - *Sposób II.* Najpierw wybieramy $k$-elementową komisję -- na $\displaystyle \binom{n}{k}$ sposobów, $1\leq k\leq n$ -- a następnie jednego z jej członków czynimy przewodniczącym -- na $k$ sposobów. Sumując po $k$, otrzymujemy $\displaystyle \sum_{k=1}^{n}k\binom{n}{k} .$ Oba sposoby liczą tę samą wielkość, więc $\displaystyle \sum_{k=1}^{n}k\binom{n}{k} = n\cdot 2^{n-1} .$ **Dowód analityczny tożsamości 2.** Różniczkując stronami wzór Newtona $\displaystyle \sum_{k=0}^{n}\binom{n}{k}x^k=(1+x)^n$ względem $x$, otrzymujemy ```{math} \sum_{k=1}^{n}k\binom{n}{k}x^{k-1}=n(1+x)^{n-1}. ``` Podstawiając $x=1$, dostajemy $\displaystyle\sum_{k=1}^{n}k\binom{n}{k}=n\cdot 2^{n-1} .$ ::: :::{prf:remark} 1. Jak już wiemy, tożsamość 1. wynika natychmiast ze wzoru Newtona dla $a=b=1 .$ 2. Tożsamość 3. otrzymujemy ze wzoru dwumianowego Newtona, przyjmując $a=1$ oraz $b=-1 .$ Oznacza ona, że suma współczynników dwumianowych na pozycjach parzystych jest równa sumie na pozycjach nieparzystych: ```{math} \binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \cdots = \binom{n}{1} + \binom{n}{3} + \binom{n}{5} + \cdots ``` 3. Tożsamość 4. otrzymujemy ze wzoru dwumianowego Newtona, przyjmując $a=1$ oraz $b=2 .$ 4. Tożsamość 5. jest szczególnym przypadkiem tożsamości Vandermonde'a. ::: :::{prf:theorem} Tożsamość Vandermonde'a Dla dowolnych nieujemnych liczb całkowitych $m, n, r$ takich, że $r \le m$ oraz $r \le n$: ```{math} \binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{r-k}\binom{n}{k}. ``` ::: :::{proof} :class: [proof] dropdown Chcemy wybrać **$r$ osób** z grupy złożonej z **$m$ kobiet** i **$n$ mężczyzn** (łącznie $m + n$ osób). Liczba wszystkich możliwych sposobów takiego wyboru z definicji wynosi **$\binom{m+n}{r}$**. Podzielmy ten wybór na rozłączne przypadki ze względu na liczbę wybranych mężczyzn (oznaczmy ją jako $k$): - Możemy wybrać **$k$ mężczyzn** spośród $n$ dostępnych na $\binom{n}{k}$ sposobów. - Wtedy pozostałe **$r - k$ osób** muszą stanowić kobiety wybrane spośród $m$ dostępnych, co robimy na $\binom{m}{r-k}$ sposobów. Z reguły mnożenia, dla ustalonej liczby mężczyzn $k$, wybór ten można wykonać na **$ \binom{m}{r-k}\binom{n}{k}$** sposobów. Ponieważ liczba wybranych mężczyzn $k$ może wynosić od $0$ do $r$, sumujemy możliwości po wszystkich możliwych wartościach $k$: $$\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{r-k} \binom{n}{k}$$ Oba sposoby zliczają dokładnie te same wybory, co kończy dowód. ::: :::{prf:theorem} Tożsamość "kija hokejowego" -- sumowania równoległego Dla nieujemnych liczb całkowitych $n, r$ takich, że $r \le n$: ```{math} \sum_{j=r}^{n}\binom{j}{r} = \binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}. ``` ::: ## Wzór włączeń i wyłączeń :::{prf:theorem} :label: thm-inclusion-exclusion Dla dowolnych zbiorów skończonych $A_1,\ldots,A_n\subseteq X$ zachodzi ```{math} |A_1\cup\cdots\cup A_n| = \sum_{i}|A_i| - \sum_{i