Z Skrypty dla studentów Ekonofizyki UPGOW

---

Wersja z 08:17, 9 gru 2013

Spis treści 1 Permutacja 1.1 Bez powtórzeń 1.2 Z powtórzeniami 2 Symbol Newtona 2.1 Metody obliczenia symbolu Newtona 2.1.1 Metoda rekursywna 2.1.2 Metoda multiplikatywna 2.1.3 Metoda Iteracyjna 2.2 Zastosowanie w kombinatoryce i statystyce 3 Kombinacja 3.1 Bez powtórzeń 3.2 Z powtórzeniami 3.3 Przykład 4 Wariacja 4.1 Bez powtórzeń 4.2 Z powtórzeniami 5 Proste związki 6 Zadania

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ń

Z powtórzeniami

Proste związki

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?