|
|
| (Nie pokazano 3 wersji pomiędzy niniejszymi.) |
| Linia 1: |
Linia 1: |
| - | == Permutacja ==
| + | '''W przygotowaniu''' |
| - | 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:
| + | |
| - | :<math>P_n=n!</math>
| + | |
| - | 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 <math>A={a_1,a_2,\ldots,a_k}</math>. Permutacja ''n'' elemtową z powtórzeniami w której elementy <math>a_1,a_2,\ldots,a_k</math> powtarzają się odpowiednio <math>n_1,n_2,\ldots,n_k</math> razy, przy czym <math>n=n_1+n_2+\ldots+n_k</math>, jest każdy ''n''-wyrazowy ciąg, w którym elementy <math>a_1,a_2,\ldots,a_k</math> powtarzają się podaną liczbę razy.
| + | |
| - | Liczba takich permutacji z powtórzeniami wynosi:
| + | |
| - | :<math>\frac{n!}{n_1!\cdot n_2! \cdot \ldots \cdot n_k!}</math>
| + | |
| - | | + | |
| - | Co ciekawe
| + | |
| - | :<math>P_n=n!=\frac{n!}{1!\cdot 1! \cdot \ldots \cdot 1!}</math>, 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:
| + | |
| - | :<math>\binom{n}{k}</math>
| + | |
| - | czytany n nad k, n po k lub k z n, jest to funkcja dwóch argumentów całkowitych nieujemnych, zdefiniowana jako:
| + | |
| - | | + | |
| - | :<math>\binom nk=\frac{n!}{k!(n-k)!}</math>
| + | |
| - | | + | |
| - | === Metody obliczenia symbolu Newtona ===
| + | |
| - | ==== Metoda rekursywna ====
| + | |
| - | :<math> \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,</math>
| + | |
| - | | + | |
| - | ponadto zachodzi:
| + | |
| - | | + | |
| - | :<math>\binom n0 = \binom nn = 1 \quad \text{dla wszystkich całkowitych } n\ge0,</math>
| + | |
| - | | + | |
| - | ==== Metoda multiplikatywna ====
| + | |
| - | :<math>\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},</math>
| + | |
| - | ==== Metoda Iteracyjna ====
| + | |
| - | :<math> \binom nk = \frac{n!}{k!\,(n-k)!} \quad \text{for }\ 0\leq k\leq n,</math>
| + | |
| - | | + | |
| - | === Zastosowanie w kombinatoryce i statystyce ===
| + | |
| - | <ul>
| + | |
| - | <li>Jest <math>\binom nk</math> sposobów na wybranie ''k'' elementów ze zbioru ''n'' elementowego,
| + | |
| - | <li> Jest <math> \binom{n+k-1}{k}</math> sposobów na wybranie ''k'' elementów ze zbioru ''n'' elementowego z powtórzeniami,
| + | |
| - | <li> Jest <math>\frac{\binom {2n}{n}}{n+1}</math> liczba Catalan'a
| + | |
| - | </ul>
| + | |
| - | == 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:
| + | |
| - | :<math>C_n^k=\binom nk = \frac{n!}{k!\,(n-k)!} =\frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1},</math>
| + | |
| - | === 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:
| + | |
| - | :<math> \bar{C}_n^k=\binom{k+n-1}{k}=\frac{(k+n-1)!}{k!(n-1)!}</math>
| + | |
| - | === Przykład ===
| + | |
| - | Oblicz na ile sposobów można wyciągnąć pięć kart z tali 52 kart
| + | |
| - | :<math> {52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311,875,200}{120} =
| + | |
| - | 2,598,960.</math>
| + | |
| - | | + | |
| - | == 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:
| + | |
| - | : <math>V_n^k = {n! \over (n-k)!} = n \cdot (n-1) \cdot ... \cdot (n-k+1)</math>
| + | |
| - | | + | |
| - | === 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
| + | |
| - | | + | |
| - | : <math>\overline{V}_{n}^k = n^k</math>
| + | |
| - | | + | |
| - | Przykład
| + | |
| - | Z liczb <math>1,2,3,4</math> można utworzyć <math>4^2=16</math> liczb dwucyfrowych.
| + | |
| - | | + | |
| - | == Proste związki ==
| + | |
| - | :<math>V_n^k=C_n^k \cdot P_k</math>
| + | |
| - | :<math>V_n^{n-1}=V_n^n=P_n</math>
| + | |
| - | | + | |
| - | == Zadania ==
| + | |
| - | #Jaka jest liczba permutacji, w którym 1 poprzedza 2
| + | |
| - | #Jaka jest liczba słów długości k w n literowym alfabecie gdy dwie kolejne litery nie są takie same,
| + | |
| - | #Ile jest wszystkich liczb naturalnych dwucyfrowych, które są podzielne przez 6 lub przez 10
| + | |
| - | #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?
| + | |
| - | #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.
| + | |
| - | #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:
| + | |
| - | ##y jest podzielne przez 23, a y nie jest podzielne przez 23?
| + | |
| - | ##x i y jest podzielne przez 23?
| + | |
| - | #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
| + | |
| - | ##dowolnych liczb?
| + | |
| - | ##liczb podzielnych przez 25?
| + | |
| - | #le permutacji można utworzyć wybierając 3 różne cyfry ze zbioru cyfr od 0 do 9?
| + | |
| - | # Encyklopedia ma 8 woluminów. Na ile sposobów można ułożyć encyklopedie na półce.
| + | |
| - | #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?
| + | |