Kombinatoryka

Zawartość

8. Kombinatoryka#

8.1. Permutacje#

Narration

Niech \(X, Y\) będą zbiorami skończonymi.

Definicja 8.1

Funkcja \(f : X\to Y\) jest bijekcją, jeśli jest:

injekcją (funkcją różnowartościową), czyli

\[\forall x_1,x_2\in X \; (x_1\neq x_2\;\imply\; f(x_1)\neq f(x_2))\]
surjekcją (funkcją „na”), czyli

\[\forall y\in Y \; \exists x\in X\; y=f(x).\]

Definicja 8.2

Permutacją zbioru \(X\) nazywamy dowolną bijekcję

\[\pi : X \to X.\]

Permutację zbioru \(X=\{a_1,\ldots,a_n\}\) zapisujemy w postaci tablicy

\[\begin{split}\pi = \begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ \pi(a_1) & \pi(a_2) & \cdots & \pi(a_n) \end{pmatrix}.\end{split}\]

Zbiór wszystkich permutacji zbioru \(X\) oznaczamy \(S_X\), a w przypadku \(X=\{1,\ldots,n\}\) – symbolem \(S_n .\)

Stwierdzenie 8.1

Liczba wszystkich permutacji \(n\)-elementowego zbioru \(X\) wynosi \(|S_X| = n! .\)

Przykład 8.1

Na każdym zbiorze skończonym \(X\) istnieje permutacja identycznościowa:

\[ \id_X : X \to X, \quad \id_X(x) = x. \]
Zbiór \(S_2\) składa się z dwóch permutacji:

\[\begin{split} \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} \end{split}\]
Zbiór \(S_3\) składa się z \(3!=6\) permutacji:

\[\begin{split} \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} \end{split}\]

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. \]

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

Definicja 8.3

Złożeniem permutacji \(\pi, \sigma \in S_X\) nazywamy permutację \(\pi\circ\sigma \in S_X\) zadaną wzorem

\[(\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 .\)

Uwaga 8.1

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\):

\[\begin{split}\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}.\end{split}\]

Definicja 8.4

Permutacją odwrotną do permutacji \(\pi \in S_X\) nazywamy funkcję odwrotną \(\pi^{-1} \in S_X\), czyli permutację spełniającą

\[\pi^{-1}\circ\pi = \pi\circ\pi^{-1} = \id_X.\]

Ponieważ \(\pi\) jest bijekcją, permutacja odwrotna \(\pi^{-1}\) zawsze istnieje i jest wyznaczona jednoznacznie.

Uwaga 8.2

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

\[\begin{split}\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}.\end{split}\]

Przykład 8.2

Dla

\[\begin{split}\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}\end{split}\]

mamy

\[\begin{split}\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},\end{split}\]

czyli \(\pi\circ\sigma\neq\sigma\circ\pi .\) Ponadto

\[\begin{split}\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}.\end{split}\]

Uwaga 8.3

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.

8.1.2. Rozkład na cykle#

Definicja 8.5

Cyklem długości \(k\) nazywamy permutację \(\pi\colon X\to X\), oznaczaną \((a_1\,a_2\,\ldots\,a_k)\), taką że

\[\begin{split}\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\}. \\\end{split}\]

Cykl długości \(2\) nazywamy transpozycją .

Cykle \((a_1\,\ldots\,a_k)\) i \((b_1\,\ldots\,b_l)\) nazywamy rozłącznymi , jeśli \(\{a_1,\ldots,a_k\}\cap\{b_1,\ldots,b_l\}=\emptyset .\)

Przykład 8.3

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

\[\begin{split}(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.\end{split}\]

Definicja 8.6

Dla permutacji \(\pi\colon X\to X\) i \(a\in X\), orbitą elementu \(a\) ze względu na \(\pi\) nazywamy zbiór

\[O(a) := \Set{\pi^k(a) : k\in\nn}.\]

Elementy jednej orbity tworzą pewien cykl permutacji \(\pi .\)

Przykład 8.4

Dla cyklu \((2\,7\,1\,5)\in S_9\) z powyższego przykładu mamy

\[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ę.
Dla

\[\begin{split}\pi=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&6&8&1&9&2&5&4&7\end{pmatrix}\end{split}\]

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) .\)

Twierdzenie 8.2

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.

Przykład 8.5

Permutacja \(\pi\) z poprzedniego przykładu rozkłada się jako

\[\pi = (1\,3\,8\,4)\circ(2\,6)\circ(5\,9\,7).\]

Twierdzenie 8.3

Każdy cykl długości \(k\) jest złożeniem \(k-1\) transpozycji (niekoniecznie rozłącznych):

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

Przykład 8.6

Dla przykładu:

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

\[\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.

8.1.3. Znak i parzystość#

Twierdzenie 8.4

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.

Definicja 8.7

Liczbę \((-1)^r\), gdzie \(\pi\) jest złożeniem \(r\) transpozycji, nazywamy znakiem permutacji \(\pi\) i oznaczamy \(\sgn\pi .\)

Permutację \(\pi\) nazywamy:

parzystą, gdy \(\sgn\pi=1\)
zaś nieparzystą, gdy \(\sgn\pi=-1 .\)

Przykład 8.7

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

Uwaga 8.4

Identyczność jest permutacją parzystą.
Złożenie dwóch permutacji parzystych jest permutacją parzystą; złożenie permutacji parzystej i nieparzystej jest nieparzyste.
Permutacja odwrotna do parzystej jest parzysta.
Cykl długości \(k\) jest permutacją parzystą, gdy \(k\) jest liczbą nieparzystą, oraz permutacją nieparzystą, gdy \(k\) jest liczbą parzystą.
Dla \(n\geq 2\), zbiór \(A_n\subseteq S_n\) wszystkich permutacji parzystych ma \(|A_n|=\dfrac{n!}{2}\) elementów.
Parzystość permutacji \(\pi\in S_n\) można też odczytać z liczby inwersji – par \((\pi(i),\pi(j))\) takich, że \(i<j\) oraz \(\pi(i)>\pi(j) .\)

Permutacja \(\pi\) jest parzysta wtedy i tylko wtedy, gdy liczba jej inwersji jest parzysta.

Na przykład dla

\[\begin{split} \pi = \begin{pmatrix}1&2&3&4&5\\3&5&2&1&4\end{pmatrix} \end{split}\]

inwersjami są pary \((3,2),\ (3,1),\ (5,2),\ (5,1),\ (5,4),\ (2,1)\), czyli jest ich \(6\), więc \(\pi\) jest parzysta.

8.2. Wariacje i kombinacje#

Narration

Niech \(S\) będzie zbiorem \(n\)-elementowym i niech \(r\in\nn_0 .\)

Definicja 8.8

Permutacją zbioru \(S\) nazywamy uporządkowany ciąg wszystkich elementów zbioru \(S .\)
Wariacją 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
Wariacją (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ć.
\(r\)-kombinacją 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\)).

Przykład 8.8

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

Stwierdzenie 8.5

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

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

\[V(n,r) = n^r.\]

Uwaga 8.5

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!\, . \]

Ćwiczenie 8.1

Ile jest możliwych czteroliterowych „słów” (bez wymogu sensowności) utworzonych z liter \(\Set{A,B,C,D,E}\), jeśli:

litery nie mogą się powtarzać,
litery mogą się powtarzać?

Rozwiązanie

Mamy zbiór \(5\)-elementowy, z którego wybieramy uporządkowane ciągi długości \(4 .\)

Litery bez powtórzeń – liczba wariacji bez powtórzeń:

\[ P(5,4) = 5\cdot 4\cdot 3\cdot 2 = 120.\]
Litery z powtórzeniami – liczba wariacji z powtórzeniami:

\[ V(5,4) = 5^4 = 625.\]

Ćwiczenie 8.2

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?

Rozwiązanie

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ć):

\[ V(10,3) = 10^3 = 1000.\]
Tablic o wszystkich cyfrach różnych:

\[ P(10,3) = 10\cdot 9\cdot 8 = 720.\]

Stwierdzenie 8.6

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:

\[C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}.\]

Uwaga 8.6

Między liczbą \(r\)-kombinacji a liczbą wariacji bez powtórzeń zachodzi prosty związek:

\[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:

wybieramy \(r\)-elementowy podzbiór zbioru \(S\) (czyli \(r\)-kombinację) – na \(C(n,r)\) sposobów,
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).

Ćwiczenie 8.3

Na ile sposobów można wybrać \(6\)-osobową załogę do misji kosmicznej spośród \(30\) wyszkolonych kandydatów?

Rozwiązanie

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:

\[\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.\]

8.3. Współczynniki dwumianowe i trójkąt Pascala#

Definicja 8.9

Dla \(0\leq k\leq n\), liczbę

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

nazywamy współczynnikiem dwumianowym (czytamy: „\(n\) nad \(k\)”). Zgodnie z poprzednim paragrafem, \(\binom{n}{k}\) jest liczbą \(k\)-elementowych podzbiorów zbioru \(n\)-elementowego.

Uwaga 8.7

Dla dowolnego \(n\in n\) oraz \(0\leq k\leq n\):

\(\binom{n}{0}=\binom{n}{n}=1\)
\(\binom{n}{1}=\binom{n}{n-1}=n\)
\(\binom{n}{k}=\binom{n}{n-k}\)
\(\binom{n}{2}=\dfrac{n(n-1)}{2}=1+2+\cdots+(n-1)\)

Stwierdzenie 8.7 (Wzór Pascala)

Dla \(0\leq k\leq n\) zachodzi

\[\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}.\]

Dowód kombinatoryczny

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}\]

Uwaga 8.8

Wzór Pascala pozwala obliczać kolejne współczynniki dwumianowe rekurencyjnie i ustawić je w trójkąt Pascala , w którym każdy wpis (poza brzegowymi jedynkami) jest sumą dwóch wpisów bezpośrednio nad nim:

\[\begin{split} \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} \end{split}\]

Stwierdzenie 8.8 (Wzór dwumianowy Newtona)

Dla dowolnych liczb \(a,b\) oraz \(n\in n\):

\[(a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k.\]

Uwaga 8.9

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{split} \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} \end{split}\]

Zauważmy, że jest to jednocześnie liczba wszystkich podzbiorów zbioru \(n\)-elementowego, czyli \(|2^X| = 2^n\) dla \(|X|=n .\)

8.4. Tożsamości kombinatoryczne#

Twierdzenie 8.9

Dla dowolnego \(n\in\nn\):

\(\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n\)
\(\displaystyle\sum_{k=1}^{n}k\binom{n}{k}=n\cdot 2^{n-1}\)
\(\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0 \quad \text{dla } n \ge 1\)
\(\displaystyle\sum_{k=0}^{n}2^k\binom{n}{k}=3^n\)
\(\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2=\binom{2n}{n} .\)

Dwa dowody tożsamości 2.

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

\[\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} .\)

Uwaga 8.10

Jak już wiemy, tożsamość 1. wynika natychmiast ze wzoru Newtona dla \(a=b=1 .\)
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:

\[\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \cdots = \binom{n}{1} + \binom{n}{3} + \binom{n}{5} + \cdots\]
Tożsamość 4. otrzymujemy ze wzoru dwumianowego Newtona, przyjmując \(a=1\) oraz \(b=2 .\)
Tożsamość 5. jest szczególnym przypadkiem tożsamości Vandermonde’a.

Twierdzenie 8.10 (Tożsamość Vandermonde’a)

Dla dowolnych nieujemnych liczb całkowitych \(m, n, r\) takich, że \(r \le m\) oraz \(r \le n\):

\[\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{r-k}\binom{n}{k}.\]

Dowód

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.

Twierdzenie 8.11 (Tożsamość „kija hokejowego” – sumowania równoległego)

Dla nieujemnych liczb całkowitych \(n, r\) takich, że \(r \le n\):

\[\sum_{j=r}^{n}\binom{j}{r} = \binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}.\]

8.5. Wzór włączeń i wyłączeń#

Twierdzenie 8.12

Dla dowolnych zbiorów skończonych \(A_1,\ldots,A_n\subseteq X\) zachodzi

\[|A_1\cup\cdots\cup A_n| = \sum_{i}|A_i| - \sum_{i<j}|A_i\cap A_j| + \sum_{i<j<k}|A_i\cap A_j\cap A_k| - \cdots + (-1)^{n+1}|A_1\cap\cdots\cap A_n|.\]

Dowód

Wystarczy pokazać, że każdy element \(a\in A_1\cup\cdots\cup A_n\) jest po prawej stronie liczony dokładnie raz.

Niech \(m\geq 1\) będzie liczbą zbiorów \(A_i\) zawierających \(a .\)

Zauważmy, że w \(r\)-tym składniku

\[ \sum_{i_1<\cdots<i_r}|A_{i_1}\cap \ldots \cap A_{i_r}| \]

element \(a\) jest liczony \(\binom{m}{r}\) razy – tyle jest sposobów wybrania \(r\) zbiorów spośród tych \(m\) zbiorów, które zawierają \(a\), które po przecięciu będą zawierały ten element.

Stąd, po prawej stronie wzoru włączeń i wyłączeń element \(a\) jest liczony

\[\binom{m}{1}-\binom{m}{2}+\binom{m}{3}-\cdots+(-1)^{m+1}\binom{m}{m}\]

razy. Ze wzoru dwumianowego dla \((1-1)^m=0\) (przy \(m\geq 1\)) mamy

\[0=\sum_{j=0}^{m}(-1)^j\binom{m}{j} = \binom{m}{0}-\binom{m}{1}+\binom{m}{2}-\cdots+(-1)^m\binom{m}{m},\]

skąd \(\binom{m}{1}-\binom{m}{2}+\cdots+(-1)^{m+1}\binom{m}{m}=\binom{m}{0}=1\), czyli element \(a\) jest po prawej stronie liczony dokładnie raz.

Ćwiczenie 8.4

Ile jest liczb naturalnych od \(1\) do \(300\) podzielnych przez \(2\), przez \(3\) lub przez \(5\)?

Rozwiązanie

Niech \(A,B,C\subseteq\{1,\ldots,300\}\) będą zbiorami liczb podzielnych odpowiednio przez \(2,3,5 .\) Wówczas

\[|A|=150,\quad |B|=100,\quad |C|=60,\]

gdyż \(A\cap B\) to liczby podzielne przez \(\mathrm{NWW}(2,3)=6\), itd. Ze wzoru włączeń i wyłączeń:

\[|A\cup B\cup C| = 150+100+60 - 50-30-20 + 10 = 220.\]

Zatem jest \(220\) liczb podzielnych przez \(2\), \(3\) lub \(5 .\)