|
|
| Linia 1: |
Linia 1: |
| - | [[Category:KURS MATEMATYKI]]
| + | '''W przygotowaniu''' |
| - | 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.
| + | |