Z Skrypty dla studentów Ekonofizyki UPGOW

Nie masz uprawnień do edytowania tej strony, z następującego powodu:

Tekst źródłowy strony można podejrzeć i skopiować.

[[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 == 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 <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> gdzie symbol ''n'' silnia <math>n!</math> jest iloczynem kolejnych liczb naturalnych aż do ''n'' :<math>n!=1 \cdot 2 \cdot 3 \cdot \ldots \cdot n</math> 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: :<math>\frac{n!}{n_1!\cdot n_2! \cdot \ldots \cdot n_k!}</math> I oczywiście otrzymujemy :<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. == 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 <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. 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> === 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 <math> \bar{C}_n^k</math> wyraża się następującym wzorem: :<math> \bar{C}_n^k=\binom{k+n-1}{k}=\frac{(k+n-1)!}{k!(n-1)!}</math> == 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 <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> Zachodzi nastepujący związek pomiędzy liczbą wariacji bez powtórzeń, liczbą kombinacji i liczbą permutacji :<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 : <math>W_n^k = n^k</math> 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: :<math>W_8^7=8^7=2097152</math> == Zadania == #Jaka jest liczba słów długości k w n literowym alfabecie jeżeli 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 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? #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. #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: ##x jest podzielne przez 23, a y nie jest podzielne przez 23? ##x i y jest podzielne przez 23? #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? ##liczb podzielnych przez 25? #Ile permutacji można utworzyć wybierając 3 różne cyfry ze zbioru cyfr od 0 do 9? # Encyklopedia ma 8 tomów. Na ile sposobów można ułożyć tomy encyklopedii na półce.

Wróć do strony Kombinatoryka.