Kombinatoryka

Z Skrypty dla studentów Ekonofizyki UPGOW

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”