Kombinatoryka

Z Skrypty dla studentów Ekonofizyki UPGOW

(Różnice między wersjami)
(Utworzył nową stronę „== Permutacja == W matematyce pojęcie permutacji dotyczy aktu permutowania (przestawienia) obiektów lub wartości. Nieformalnie, permutacją zbioru obiektów jest roz...”)
(UWAGA! Zastąpienie treści hasła bardzo krótkim tekstem: „'''W przygotowaniu'''”)
 
(Nie pokazano 4 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ń ===
+
-
=== Z powtórzeniami ===
+
-
== Proste związki ==
+
-
== 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?
+

Aktualna wersja na dzień 08:28, 17 mar 2014

W przygotowaniu