Kombinatoryka

Z Skrypty dla studentów Ekonofizyki UPGOW

(Różnice między wersjami)
Linia 1: Linia 1:
[[Category:KURS MATEMATYKI]]
[[Category:KURS MATEMATYKI]]
 +
W rozważaniu pojęć z kombinatoryki należy zwrócić uwagę na to czy istotna jest kolejność elementów w zbiorze. Jeżeli jest istotna to mamy do czynienia z ciągiem, a jeżeli nie jest istotna to rozpatrujemy zbiory lub podzbiory. Ponadto musimy odpowiedzieć na pytanie czy elementy mogą się powtarzać, czy mają być różne. 
 +
== Permutacja ==
== 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.
+
Pojęcie permutacji dotyczy przestawiania (permutowania) obiektów lub wartości. Nieformalnie, permutacją zbioru obiektów jest ich rozmieszczenie w określonej kolejności.  
-
=== Bez powtórzeń ===
+
=== Permutacja 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:
+
Permutacją bez powtórzeń zbioru złożonego z <math> n </math> różnych elementów nazywamy każdy ciąg <math> n </math> wyrazowy utworzony ze wszystkich elementów zbioru. Wszystkich możliwych permutacji zbioru <math> n </math>-elementowego jest:
:<math>P_n=n!</math>
:<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}
+
gdzie symbol ''n'' silnia <math>n!</math> jest iloczynem kolejnych liczb naturalnych aż do ''n''
-
=== Z powtórzeniami ===
+
:<math>n!=1 \cdot 2 \cdot 3 \cdot \ldots \cdot n</math>
-
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.
+
przy czym z definicji <math>0!=1</math>. I oczywiście także <math>1!=1.</math>
 +
 
 +
Dla przykładu 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} oraz {3,2,1}.
 +
 
 +
=== Permutacja z powtórzeniami ===
 +
Niech <math> A </math> oznacza zbiór złożony z <math> k </math> różnych elementów <math> A </math>={<math>a_1,a_2,\ldots,a_k</math>}. Permutacją <math> n </math> elementową 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 <math> n </math>-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:
Liczba takich permutacji z powtórzeniami wynosi:
:<math>\frac{n!}{n_1!\cdot n_2! \cdot \ldots \cdot n_k!}</math>
:<math>\frac{n!}{n_1!\cdot n_2! \cdot \ldots \cdot n_k!}</math>
-
Co ciekawe
+
I oczywiście otrzymujemy
-
:<math>P_n=n!=\frac{n!}{1!\cdot 1! \cdot \ldots \cdot 1!}</math>, każdy z elementów występuje dokładnie raz.
+
:<math>P_n=n!=\frac{n!}{1!\cdot 1! \cdot \ldots \cdot 1!}</math> w przypadku gdy każdy z elementów występuje dokładnie jeden raz.
-
== Symbol Newtona ==
+
== Kombinacja ==
-
Symbol Newtona nazywany jest także współczynnikiem dwumianowym i zapisywany jest następująco:
+
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.
-
:<math>\binom{n}{k}</math>
+
=== Kombinacja bez powtórzeń ===
-
czytany n nad k, n po k lub k z n, jest to funkcja dwóch argumentów całkowitych nieujemnych, zdefiniowana jako:
+
Kombinacją k-elementową bez powtórzeń zbioru A składającego się z n różnych elementów nazywamy każdy k-elementowy podzbiór zbioru A, przy czym  0 ≤ k ≤ n.
 +
Liczba kombinacji k-elementowych bez powtórzeń w zbiorze n-elementowym <math>C_n^k</math> wyraża się następującym 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>
 +
gdzie <math>\binom nk</math> jest symbolem Newtona.
-
:<math>\binom nk=\frac{n!}{k!(n-k)!}</math>
+
Obliczymy na ile sposobów można wyciągnąć pięć kart z tali 52 kart. Kolejność wyciągniętych kart nie ma znaczenia, zatem trzeba znaleźć liczbę podzbiorów 5-cio elementowych w zbiorze 52 różnych elemetów. Jest to kombinacja bez powtórzeń. 
 +
:<math> C_{52}^5 = {52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311,875,200}{120} =
 +
2,598,960.</math>
-
=== Metody obliczenia symbolu Newtona ===
+
=== Kombinacja z powtórzeniami ===
-
==== Metoda rekursywna ====
+
Kombinacja ''k''-elementowa z powtórzeniami w ''n''-elementowym zbiorze ''A'' to każdy ''k''-elementowy multizbiór składający się z elementów zbioru ''A'', przy czym w  odróżnieniu od kombinacji bez powtórzeń elementy mogą się powtarzać. Multizbiór, w którym elementy mogą występować wiele razy, jest rozszerzeniem pojęcia zbioru.
-
:<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:
+
I tak np. z trzech elementów a, b, c, można utworzyć 6 dwuelementowych kombinacji z powtórzeniami: aa, ab, ac, bb, bc oraz cc.
-
:<math>\binom n0 = \binom nn = 1 \quad \text{dla wszystkich całkowitych } n\ge0,</math>
+
Możemy także utworzyć 3-elementowe kombinacje z powtórzeniami zbioru 2-elementowego a, b. Można utworzyć 4 takie trzyelementowe kombinacje z powtórzeniami: aaa, aab, abb oraz bbb. Pamiętamy, że w przypadku kombinacji kolejność elementów nie jest istotna.
-
==== Metoda multiplikatywna ====
+
Liczba k-elementowych kombinacji z powtórzeniami w zbiorze ''n''-elementowym <math> \bar{C}_n^k</math> wyraża się następującym wzorem:
-
:<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>
:<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 ==
== Wariacja ==
-
=== Bez powtórzeń ===
+
Wariacja jest to sposób wyboru kilku rzeczy z większej grupy, przy czym tak jak w przypadku permutacji kolejność ma znaczenie. Na przykład czterech zawodników A B C D może zdobyć 3 medale (złoty, srebrny i brązaowy) na 24 sposoby: ABC, ABD, ACB,... Zachęcamy czytelnika do sprawdzenia.  
-
''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:
+
=== Wariacja bez powtórzeń ===
 +
''k''-wyrazową wariacją bez powtórzeń zbioru ''n''-elementowego '''A''' (gdzie 1 ≤ ''k'' ≤ ''n'') nazywamy każdy ciąg ''k''-wyrazowy utworzony z różnych elementów tego zbioru. Jak pamiętamy kolejność elementów w ciągu jest istotna. Gdy ''k''=''n'' wariacja bez powtórzeń staje się permutacją - tworzymy ciągi ze wszystkich ''n'' elementów zbioru.
 +
 
 +
Liczba wszystkich ''k''-wyrazowych wariacji bez powtórzeń zbioru ''n''-elementowego <math>V_n^k</math> wyraża się następującym wzorem:
: <math>V_n^k = {n! \over (n-k)!} = n \cdot (n-1) \cdot ... \cdot (n-k+1)</math>
: <math>V_n^k = {n! \over (n-k)!} = n \cdot (n-1) \cdot ... \cdot (n-k+1)</math>
-
=== Z powtórzeniami ===
+
Zachodzi nastepujący związek pomiędzy liczbą wariacji bez powtórzeń, liczbą kombinacji i liczbą permutacji
-
''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.
+
 
 +
:<math>V_n^k=C_n^k \cdot P_k</math>
 +
 
 +
=== Wariacja z powtórzeniami ===
 +
''k''-elementową wariacją z powtórzeniami zbioru ''n''-elementowego <math>W_n^k</math> nazywamy każdy ''k''-wyrazowy ciąg elementów tego zbioru, przy czym dowolny element zbioru może wystąpić wielokrotnie w ciągu. Należy zauważyć, że wariacja z powtórzeniami jest ciągiem co oznacza, że kolejność elementów ma znaczenie.
Liczba wszystkich ''k''-wyrazowych wariacji z możliwymi powtórzeniami zbioru ''n''-elementowego jest równa
Liczba wszystkich ''k''-wyrazowych wariacji z możliwymi powtórzeniami zbioru ''n''-elementowego jest równa
-
: <math>\overline{V}_{n}^k = n^k</math>
+
: <math>W_n^k = n^k</math>
-
=== Przykład ===
+
Obliczymy ile jest siedmiocyfrowych numerów telefonów nie zawierających cyfr 0 i 1. Cyfry w numerze telefonu mogą sie powtarzać i oczywiście istotna jest ich kolejność. Jest to zatem wariacja siedmioelementowa (numer siedmiocyfrowy) w zbiorze osmioelementowym (osiem cyfr). Otrzymujemy:
-
Z liczb <math>1,2,3,4</math> można utworzyć <math>4^2=16</math> liczb dwucyfrowych.
+
-
== Proste związki ==
+
:<math>W_8^7=8^7=2097152</math>
-
:<math>V_n^k=C_n^k \cdot P_k</math>
+
-
:<math>V_n^{n-1}=V_n^n=P_n</math>
+
== Zadania ==
== Zadania ==
-
#Jaka jest liczba permutacji, w którym 1 poprzedza 2
+
#Jaka jest liczba słów długości k w n literowym alfabecie jeżeli dwie kolejne litery nie są takie same?
-
#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?
-
#Ile jest wszystkich liczb naturalnych dwucyfrowych, które są podzielne przez 6 lub przez 10
+
#Cztery dziewczynki i sześciu chłopców siedzi na ławce. Dziewczynki siedzą obok siebie i chłopcy również siedzą obok siebie. Ile jest wszystkich możliwych sposobów posadzenia dzieci w taki sposób?
-
#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 których występuje dokładnie trzy razy cyfra 0 i dokładnie jeden raz występuje cyfra 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.
+
#Spośród liczb {1,2,3,...,1000} losujemy jednocześnie dwie, które oznaczamy x  i y . Ile jest możliwości wylosowania takiej pary liczb (x,y) dla której:
-
#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:
+
##x jest podzielne przez 23, a y  nie jest podzielne przez 23?
-
##y jest podzielne przez 23, a y  nie jest podzielne przez 23?
+
##x i y  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
+
#Ze zbioru dziesięciu cyfr {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?
##dowolnych liczb?
##liczb podzielnych przez 25?
##liczb podzielnych przez 25?
-
#le permutacji można utworzyć wybierając 3 różne cyfry ze zbioru cyfr od 0 do 9?
+
#Ile 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.
+
# Encyklopedia ma 8 tomów. Na ile sposobów można ułożyć tomy encyklopedii 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?
+

Wersja z 20:00, 6 mar 2014

W rozważaniu pojęć z kombinatoryki należy zwrócić uwagę na to czy istotna jest kolejność elementów w zbiorze. Jeżeli jest istotna to mamy do czynienia z ciągiem, a jeżeli nie jest istotna to rozpatrujemy zbiory lub podzbiory. Ponadto musimy odpowiedzieć na pytanie czy elementy mogą się powtarzać, czy mają być różne.

Spis treści

Permutacja

Pojęcie permutacji dotyczy przestawiania (permutowania) obiektów lub wartości. Nieformalnie, permutacją zbioru obiektów jest ich rozmieszczenie w określonej kolejności.

Permutacja bez powtórzeń

Permutacją bez powtórzeń zbioru złożonego z \( n \) różnych elementów nazywamy każdy ciąg \( n \) wyrazowy utworzony ze wszystkich elementów zbioru. Wszystkich możliwych permutacji zbioru \( n \)-elementowego jest: \[P_n=n!\] gdzie symbol n silnia \(n!\) jest iloczynem kolejnych liczb naturalnych aż do n \[n!=1 \cdot 2 \cdot 3 \cdot \ldots \cdot n\] przy czym z definicji \(0!=1\). I oczywiście także \(1!=1.\)

Dla przykładu 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} oraz {3,2,1}.

Permutacja 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\)}. Permutacją \( n \) elementową 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!}\]

I oczywiście otrzymujemy \[P_n=n!=\frac{n!}{1!\cdot 1! \cdot \ldots \cdot 1!}\] w przypadku gdy każdy z elementów występuje dokładnie jeden raz.

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.

Kombinacja bez powtórzeń

Kombinacją k-elementową bez powtórzeń zbioru A składającego się z n różnych elementów nazywamy każdy k-elementowy podzbiór zbioru A, przy czym 0 ≤ k ≤ n. Liczba kombinacji k-elementowych bez powtórzeń w zbiorze n-elementowym \(C_n^k\) wyraża się następującym wzorem: \[C_n^k=\binom nk = \frac{n!}{k!\,(n-k)!} =\frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1},\] gdzie \(\binom nk\) jest symbolem Newtona.

Obliczymy na ile sposobów można wyciągnąć pięć kart z tali 52 kart. Kolejność wyciągniętych kart nie ma znaczenia, zatem trzeba znaleźć liczbę podzbiorów 5-cio elementowych w zbiorze 52 różnych elemetów. Jest to kombinacja bez powtórzeń. \[ C_{52}^5 = {52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311,875,200}{120} = 2,598,960.\]

Kombinacja z powtórzeniami

Kombinacja k-elementowa z powtórzeniami w n-elementowym zbiorze A to każdy k-elementowy multizbiór składający się z elementów zbioru A, przy czym w odróżnieniu od kombinacji bez powtórzeń elementy mogą się powtarzać. Multizbiór, w którym elementy mogą występować wiele razy, jest rozszerzeniem pojęcia zbioru.

I tak np. z trzech elementów a, b, c, można utworzyć 6 dwuelementowych kombinacji z powtórzeniami: aa, ab, ac, bb, bc oraz cc.

Możemy także utworzyć 3-elementowe kombinacje z powtórzeniami zbioru 2-elementowego a, b. Można utworzyć 4 takie trzyelementowe kombinacje z powtórzeniami: aaa, aab, abb oraz bbb. Pamiętamy, że w przypadku kombinacji kolejność elementów nie jest istotna.

Liczba k-elementowych kombinacji z powtórzeniami w zbiorze n-elementowym \( \bar{C}_n^k\) wyraża się następującym wzorem: \[ \bar{C}_n^k=\binom{k+n-1}{k}=\frac{(k+n-1)!}{k!(n-1)!}\]

Wariacja

Wariacja jest to sposób wyboru kilku rzeczy z większej grupy, przy czym tak jak w przypadku permutacji kolejność ma znaczenie. Na przykład czterech zawodników A B C D może zdobyć 3 medale (złoty, srebrny i brązaowy) na 24 sposoby: ABC, ABD, ACB,... Zachęcamy czytelnika do sprawdzenia.

Wariacja bez powtórzeń

k-wyrazową wariacją bez powtórzeń zbioru n-elementowego A (gdzie 1 ≤ k ≤ n) nazywamy każdy ciąg k-wyrazowy utworzony z różnych elementów tego zbioru. Jak pamiętamy kolejność elementów w ciągu jest istotna. Gdy k=n wariacja bez powtórzeń staje się permutacją - tworzymy ciągi ze wszystkich n elementów zbioru.

Liczba wszystkich k-wyrazowych wariacji bez powtórzeń zbioru n-elementowego \(V_n^k\) wyraża się następującym wzorem:

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

Zachodzi nastepujący związek pomiędzy liczbą wariacji bez powtórzeń, liczbą kombinacji i liczbą permutacji

\[V_n^k=C_n^k \cdot P_k\]

Wariacja z powtórzeniami

k-elementową wariacją z powtórzeniami zbioru n-elementowego \(W_n^k\) nazywamy każdy k-wyrazowy ciąg elementów tego zbioru, przy czym dowolny element zbioru może wystąpić wielokrotnie w ciągu. Należy zauważyć, że wariacja z powtórzeniami jest ciągiem co oznacza, że kolejność elementów ma znaczenie.

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

\(W_n^k = n^k\)

Obliczymy ile jest siedmiocyfrowych numerów telefonów nie zawierających cyfr 0 i 1. Cyfry w numerze telefonu mogą sie powtarzać i oczywiście istotna jest ich kolejność. Jest to zatem wariacja siedmioelementowa (numer siedmiocyfrowy) w zbiorze osmioelementowym (osiem cyfr). Otrzymujemy:

\[W_8^7=8^7=2097152\]

Zadania

  1. Jaka jest liczba słów długości k w n literowym alfabecie jeżeli dwie kolejne litery nie są takie same?
  2. Ile jest wszystkich liczb naturalnych dwucyfrowych, które są podzielne przez 6 lub przez 10?
  3. Cztery dziewczynki i sześciu chłopców siedzi na ławce. Dziewczynki siedzą obok siebie i chłopcy również siedzą obok siebie. Ile jest wszystkich możliwych sposobów posadzenia dzieci w taki sposób?
  4. Oblicz, ile jest liczb naturalnych sześciocyfrowych, w których występuje dokładnie trzy razy cyfra 0 i dokładnie jeden raz występuje cyfra 5.
  5. Spośród liczb {1,2,3,...,1000} 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. x jest podzielne przez 23, a y nie jest podzielne przez 23?
    2. x i y jest podzielne przez 23?
  6. Ze zbioru dziesięciu cyfr {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?
  7. Ile permutacji można utworzyć wybierając 3 różne cyfry ze zbioru cyfr od 0 do 9?
  8. Encyklopedia ma 8 tomów. Na ile sposobów można ułożyć tomy encyklopedii na półce.
Źródło „http://172.16.3.1/ekonofizyka/index.php/Kombinatoryka”