Kombinatoryka

Z Skrypty dla studentów Ekonofizyki UPGOW

Spis treści

Permutacja

W matematyce pojęcie permutacji dotyczy aktu permutowania (przestawienia) obiektów lub wartości. Nieformalnie, permutacją zbioru obiektów jest rozmieszczenie tych obiektów w określonej kolejności. Dla przykładu, istnieje sześć permutacji w zbiorze {1,2,3}, mianowicie (1,2,3), (1,3,2), (2,1,3), (​​2,3,1), (3,1,2) i (3,2,1). Jako inny przykład można podać anagram słowa - permutacją jest przestawianie jego liter. Badania permutacji ogół należy do dziedziny kombinatoryki.

Bez powtórzeń

Permutacją bez powtórzeń zbioru złożonego z n różnych elementów nazywamy każdy n wyrazowy ciąg utworzony ze wszystkich wyrazów zbioru. Wszystkich możliwych permutacji zbioru n-elementowego jest: \[P_n=n!\] Dla przykłady elementy zbioru A={1,2,3} można ustawić na 3!=6 sposobów {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2} i {3,2,1}

Z powtórzeniami

Niech A oznacza zbiór złożony z k różnych elementów \(A={a_1,a_2,\ldots,a_k}\). Permutacja n elemtową z powtórzeniami w której elementy \(a_1,a_2,\ldots,a_k\) powtarzają się odpowiednio \(n_1,n_2,\ldots,n_k\) razy, przy czym \(n=n_1+n_2+\ldots+n_k\), jest każdy n-wyrazowy ciąg, w którym elementy \(a_1,a_2,\ldots,a_k\) powtarzają się podaną liczbę razy. Liczba takich permutacji z powtórzeniami wynosi: \[\frac{n!}{n_1!\cdot n_2! \cdot \ldots \cdot n_k!}\]

Co ciekawe \[P_n=n!=\frac{n!}{1!\cdot 1! \cdot \ldots \cdot 1!}\], każdy z elementów występuje dokładnie raz.

Symbol Newtona

Symbol Newtona nazywany jest także współczynnikiem dwumianowym i zapisywany jest następująco: \[\binom{n}{k}\] czytany n nad k, n po k lub k z n, jest to funkcja dwóch argumentów całkowitych nieujemnych, zdefiniowana jako:

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

Metody obliczenia symbolu Newtona

Metoda rekursywna

\[ \binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \text{dla wszystkich liczb całkowitych }n,k : 1\le k\le n-1,\]

ponadto zachodzi:

\[\binom n0 = \binom nn = 1 \quad \text{dla wszystkich całkowitych } n\ge0,\]

Metoda multiplikatywna

\[\binom nk = \frac{n^{\underline{k}}}{k!} = \frac{n(n-1)(n-2)\cdots(n-(k-1))}{k(k-1)(k-2)\cdots 1}=\prod_{i=1}^k \frac{n-(k-i)}{i},\]

Metoda Iteracyjna

\[ \binom nk = \frac{n!}{k!\,(n-k)!} \quad \text{for }\ 0\leq k\leq n,\]

Zastosowanie w kombinatoryce i statystyce

  • Jest \(\binom nk\) sposobów na wybranie k elementów ze zbioru n elementowego,
  • Jest \( \binom{n+k-1}{k}\) sposobów na wybranie k elementów ze zbioru n elementowego z powtórzeniami,
  • Jest \(\frac{\binom {2n}{n}}{n+1}\) liczba Catalan'a

Kombinacja

Kombinacja jest to sposób wyboru kilka rzeczy z większej grupy, w której (w przeciwieństwie do permutacji) kolejność nie ma znaczenia. Na przykład biorąc pod uwagę kule o różnych kolorach, powiedzmy białą, czarną i czerwoną, istnieją trzy kombinacje dwóch kul, które można wyciągnąć z tego zestawu: biała i czarna, biała i czerwona lub czarna i czerwona.

Bez powtórzeń

Kombinacja bez powtórzeń to każdy podzbiór zbioru skończonego, poza zbiorem pustym. Kombinacją k-elementową zbioru n-elementowego A nazywa się każdy k-elementowy podzbiór zbioru A (0 ≤ k ≤ n). Używa się też terminu "kombinacja z n elementów po k elementów" lub wręcz "kombinacja z n po k". Dopełnieniem kombinacji z n po k jest kombinacja z n po n−k. Liczba kombinacji z n po k wyraża się wzorem: \[C_n^k=\binom nk = \frac{n!}{k!\,(n-k)!} =\frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1},\]

Z powtórzeniami

Kombinacja z powtórzeniami, to każdy zbiór którego elementami są elementy pewnego zbioru skończonego. k-elementową kombinacją z powtórzeniami zbioru n-elementowego A nazywa się każdy k-elementowy multizbiór składający się z elementów zbioru A. W odróżnieniu do kombinacji bez powtórzeń tu elementy mogą się powtarzać. Liczba k-elementowych kombinacji z powtórzeniami zbioru n-elementowego wyraża się wzorem: \[ \bar{C}_n^k=\binom{k+n-1}{k}=\frac{(k+n-1)!}{k!(n-1)!}\]

Przykład

Oblicz na ile sposobów można wyciągnąć pięć kart z tali 52 kart \[ {52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311,875,200}{120} = 2,598,960.\]

Wariacja

Bez powtórzeń

k-wyrazową wariacją bez powtórzeń zbioru n-elementowego A (gdzie 1 ≤ k ≤ n) nazywa się każdy k-wyrazowy ciąg, k różnych elementów tego zbioru (kolejność tych elementów ma znaczenie). Gdy k=n, wariację bez powtórzeń nazywa się permutacj.

Liczba wszystkich k-wyrazowych wariacji bez powtórzeń zbioru n-elementowego wyraża się wzorem:

\(V_n^k = {n! \over (n-k)!} = n \cdot (n-1) \cdot ... \cdot (n-k+1)\)

Z powtórzeniami

k-wyrazową wariacją z powtórzeniami zbioru n-elementowego A nazywa się k-wyrazowy ciąg elementów tego zbioru (dowolny element może wystąpić wielokrotnie w ciągu). Należy zauważyć, iż kolejność elementów ma znaczenie.

Liczba wszystkich k-wyrazowych wariacji z możliwymi powtórzeniami zbioru n-elementowego jest równa

\(\overline{V}_{n}^k = n^k\)

Przykład Z liczb \(1,2,3,4\) można utworzyć \(4^2=16\) liczb dwucyfrowych.

Proste związki

\[V_n^k=C_n^k \cdot P_k\] \[V_n^{n-1}=V_n^n=P_n\]

Zadania

  1. Jaka jest liczba permutacji, w którym 1 poprzedza 2
  2. Jaka jest liczba słów długości k w n literowym alfabecie gdy dwie kolejne litery nie są takie same,
  3. Ile jest wszystkich liczb naturalnych dwucyfrowych, które są podzielne przez 6 lub przez 10
  4. Cztery dziewczynki i sześciu chłopców siedzą na tym samym pniu zwalonego dębu. Dziewczynki siedzą obok siebie i chłopcy również siedzą obok siebie. Ile jest wszystkich możliwych sposobów posadzenia dzieci w ten sposób?
  5. Oblicz, ile jest liczb naturalnych sześciocyfrowych, w zapisie których występuje dokładnie trzy razy cyfra 0 i dokładnie raz występuje cyfra 5.
  6. Spośród liczb {1,2,3,...,100 0} losujemy jednocześnie dwie, które oznaczamy x i y . Ile jest możliwości wylosowania takiej pary liczb (x,y) , dla której:
    1. y jest podzielne przez 23, a y nie jest podzielne przez 23?
    2. x i y jest podzielne przez 23?
  7. Ze zbioru {0,1,2,3,4,5,6 ,7 ,8,9} losujemy kolejno 4 cyfry bez zwracania, a następnie zapisujemy je w kolejności losowania tworząc liczbę 4 cyfrową. Ile można otrzymać w ten sposób
    1. dowolnych liczb?
    2. liczb podzielnych przez 25?
  8. le permutacji można utworzyć wybierając 3 różne cyfry ze zbioru cyfr od 0 do 9?
  9. Encyklopedia ma 8 woluminów. Na ile sposobów można ułożyć encyklopedie na półce.
  10. Restauracja oferuje 5 możliwości wyboru przystawki, 10 dań głównych i 4 desery.Klient może wybrać tylko jedno danie (przystawkę lub danie główne lub deser) lub dwa danie (z trzech opcji) lub cały zestaw (przystawka danie główne i deser) Zakładając, że wszystkie opcje są dostępne, jak wiele różnych możliwości posiłków oferuje restauracja?
Źródło „http://172.16.3.1/ekonofizyka/index.php/Kombinatoryka”