Kombinatoryka

Kombinatoryka stanowi dział matematyki, który zajmuje się obliczaniem liczby zbiorów, jakie można utworzyć w zadany sposób z elementów danego skończonego zbioru.

Dość często pojęcia permutacji, kombinacji, wariacji bez powtórzeń i wariacji z powtórzeniami są mylone ze sobą. W poniższej tabeli zestawione zostały podobieństwa i różnice między nimi. Tabela zawiera informacje, które ułatwią podjęcie decyzji, kiedy jaki wzór zastosować. Ponadto tablice te zawierają wszystkie podstawowe wzory z kombinatoryki.

Kombinatoryka - wzory

Niech:

Tablica

nazwa pLiczba pRodzajCzy kolejność wyrazów ma znaczenie?Czy mogą występować powtórzenia tego samego elementu zbioru?
permutacje\(P_n=n!\) tworzymy ciągi \(n\)-elementowetaknie
kombinacje\(C^{k}_{n}={n \choose k}=\frac{n!}{k!(n-k)!}\) tworzymy podzbiory \(k\)-elementowenienie
wariacje bez powtórzeń\(V^{k}_{n}=\frac{n!}{(n-k)!}\) tworzymy ciągi \(k\)-elementowe o różnych wyrazachtaknie
wariacje z powtórzeniami\(W^{k}_{n}=n^k\) tworzymy ciągi \(k\)-elementowetaktak

Kombinatoryka — przykłady

A oto tabela z przykładami \(p\) utworzonymi z elementów zbioru trzyelementowego.

nazwa p Określenie wszystkich \(p\) dla zbioru {a,b,c}
permutacje (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)
kombinacje1-elementowe: {a}, {b}, {c}
2-elementowe: {a, b}, {a, c}, {b, c}
3-elementowe: {a, b, c}
wariacje bez powtórzeń1-elementowe: (a), (b), (c)
2-elementowe: (a, b), (a, c), (b, c), (b, a), (c, a), (c, b)
3-elementowe: (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)
wariacje z powtórzeniami1-elementowe: (a), (b), (c)
2-elementowe: (a, b), (a, c), (b, c), (b, a), (c, a), (c, b), (a, a), (b, b), (c, c)
3-elementowe: (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a), (a, a, b), (a, a, c), (b, a, a), (c, a, a), (a, b, a), (a, c, a), (b, b, a), (b, b, c), (a, b, b), (c, b, b), (b, a, b), (b, c, b), (c, c, a), (c, c, b), (a, c, c), (b, c, c), (c, a, c), (c, b, c), (a, a, a), (b, b, b), (c, c, c)

Zastosowanie kombinatoryki do obliczania prawdopodobieństwa

Część zadań z rachunku prawdopodobieństwa da się sprowadzić do schematu polegającego na losowaniu \(k\) elementów z \(n\) elementów pewnego zbioru ze zwracaniem lub bez zwracania do zbioru. Takie podejście do zagadnienia pozwala korzystać z kombinatoryki podczas obliczania prawdopodobieństw.

Poniższa tabela podsumowuje wiedzę z zakresu kombinatoryki.

Oto kilka przykładów zadań z rachunku prawdopodobieństwa, w których zastosujemy elementy kombinatoryki.

Przykład 1

Obliczyć prawdopodobieństwo zdarzenia polegającego na wyrzuceniu w każdym rzucie kostką symetryczną inną liczbę oczek, w przypadku, gdy rzucamy kością 4 razy.

Zbiór zdarzeń elementarnych określamy następująco:

\(\Omega=\lbrace \omega = (k,l,m,n): k,l,m,n\in \lbrace 1,2,3,4,5,6 \rbrace \rbrace\)

Przykładowo zdarzeniem elementarnym będzie czwórka liczb \(1,4,5,3)\) lub \((6,6,6,6)\) itd. Jak obliczyć liczbę elementów zbioru zdarzeń elementarnych? Zauważ że losujemy kolejno cztery liczby ze zbioru sześciu liczb, przy czym kolejność losowania ma znaczenie, gdyż wynik \((1,2,3,4)\) jest wynikiem innym od \((4,3,2,1)\) — mamy tu dwa różne zdarzenia elementarne. Mamy losowanie ze zwracaniem, gdyż dla przykładu sześć oczek może wypaść kilka razy (czyli gdy wylosujemy sześć oczek, w kolejnym losowaniu znów można wylosować tę samą liczbę — trzeba ją więc po każdym losowaniu „zwrócić” do zbioru). Z powyższej tabeli wynika, że jeżeli mamy do czynienia z losowaniem ze zwracaniem, w którym kolejność elementów jest istotna, to do obliczenia liczby wszystkich możliwych wyników losowań w tym doświadczeniu stosujemy wariację z powtórzeniami.

Obliczamy więc 4-wyrazowe wariacje z powtórzeniami sześcioelementowego zbioru.

\(\overline{\overline{\Omega}} = W^4_6=6^4=1296\)

Zdarzenie \(A\) polega na wyrzuceniu w każdym rzucie innej liczby oczek, a więc to tak, jakby po wyrzuceniu na przykład szóstki nie zwrócić jej do zbioru i losować z pozostałych pięciu możliwych liczb. Kolejność oczywiście nadal ma znaczenie. Aby obliczyć liczbę wszystkich zdarzeń elementarnych sprzyjających zdarzeniu \(A\), skorzystamy z wariacji bez powtórzeń.

\(\overline{\overline{A}}=V^4_6=\frac{6!}{(6-4)!}=\frac{6!}{2!} = \frac{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6}{1\cdot 2} = 3\cdot 4\cdot 5\cdot 6=360\)

Obliczamy prawdopodobieństwo zdarzenia \(A\):

\(P(A)=\frac{\overline{\overline{A}}}{ \overline{ \overline{ \Omega}}} = \frac{360}{1296} = \frac{5}{18}\)

Przykład 2

W wytłaczance jest 9 jajek dobrych i 3 zepsute. Wyjęto 2 jajka. Jakie jest prawdopodobieństwo, że jajecznica z obu jajek będzie smaczna?

Zakładamy, że jajecznica jest smaczna, jeżeli powstała z dobrych jajek. Ponumerujemy jajka dobre od 1 do 9, a złe od 10 do 12. Nie ma znaczenia czy weźmiemy z wytłaczanki pierwsze a potem drugie jajko lub odwrotnie. Kolejność nie ma tu znaczenia. Jajek po wybraniu nie zwracamy do wytłaczanki, więc aby policzyć na ile sposobów możemy wylosować dwa jajka z 12 korzystamy z kombinacji dwuelementowych zbioru 12-elementowego.

\(\overline{\overline{\Omega}}=C^2_{12} = {12\choose 2}=\frac{12!}{2!(12-2)!} = \frac{12!}{2!10!}=\)

\(=\frac{10!\cdot 11\cdot 12}{2\cdot 10!}=\frac{11\cdot 12}{2}=66\)

Zdarzenie \(A\) oznacza wylosowanie 2 dobrych jajek, a więc losujemy dwa elementy ze zbioru dziewięcioelementowego (bo tyle jest dobrych jajek) i kolejność nie ma tu znaczenia, jajek nie zwracamy po losowaniu. Znów korzystamy z kombinacji.

\(\overline{\overline{A}}=C^2_9={9\choose 2}=\frac{9!}{2!(9-2)!}=\frac{9!}{2!7!} = \frac{7!\cdot 8\cdot 9}{2\cdot 7!}=\frac{72}{2}=36\)

Obliczamy prawdopodobieństwo zdarzenia \(A\):

\(P(A)=\frac{\overline{\overline{A}}}{ \overline{ \overline{\Omega}}} =\frac{36}{66}=\frac{6}{11}\)

Przykład 3

Jakie jest prawdopodobieństwo trafienia 6 w dużego lotka?

W dużym lotku losuje się bez zwracania 6 liczb z 49, kolejność nie ma znaczenia, więc zdarzeń elementarnych jest tyle ile kombinacji sześcioelementowych zbioru 49-elementowego:

\(\overline{\overline{\Omega}} = C^6_{49}={49\choose 6} = \frac{49!}{6!(49-6)!}=\frac{49!}{6!43!}=13983816\)

Zdarzenie \(A\) — wytypowanie 6-ciu liczb zachodzi w jednym przypadku.

\(\overline{\overline{A}}=1\)

Obliczamy prawdopodobieństwo zdarzenia \(A\):

\(P(A)=\frac{\overline{\overline{A}}}{ \overline{ \overline{\Omega}}} = \frac{1}{13983816}\)

Pytania

Co mają ze sobą wspólnego kombinatoryka i rachunek prawdopodobieństwa?

Otóż kombinatoryka dostarcza narzędzi do wyliczania prawdopodobieństwa pewnych zdarzeń, jeżeli tylko mamy do czynienia z losowaniem elementów z określonych zbiorów. Kombinatoryka daje pewne podstawy w rachunku prawdopodobieństwa.

Jakie ma zastosowanie kombinatoryka?

Kombinatoryka powstała w XVI wieku wraz z grami hazardowymi i w grach hazardowych ma praktyczne zastosowanie. Oprócz tego jest stosowana w informatyce, rachunku prawdopodobieństwa, w teorii liczb i teorii grafów.



Zadania z rozwiązaniami

zadanie maturalne

Zadanie nr 1.

Ile słów czteroliterowych (niekoniecznie mających znaczenie) można utworzyć z 32 liter alfabetu, używając każdej z liter tylko raz?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 2 — maturalne.

Dokończ zdanie. Wybierz właściwą odpowiedź spośród podanych. Wszystkich liczb naturalnych pięciocyfrowych, w których zapisie dziesiętnym występują tylko cyfry 0, 5, 7 (np. 57 075, 55 555), jest

A. \(5^3\)

B. \(2\cdot 4^3\)

C. \(2\cdot 3^4\)

D. \(3^5\)

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 3 — maturalne.

Wszystkich różnych liczb naturalnych czterocyfrowych nieparzystych podzielnych przez 5 jest

A. 9·8·7·2

B. 9·10·10·1

C. 9·10·10·2

D. 9·9·8·1

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 4 — maturalne.

Wszystkich liczb naturalnych trzycyfrowych, większych od 700, w których każda cyfra należy do zbioru {1, 2, 3, 7, 8, 9} i żadna cyfra się nie powtarza, jest

A. 108

B. 60

C. 40

D. 299

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 5 — maturalne.

Oblicz, ile jest wszystkich siedmiocyfrowych liczb naturalnych, w których zapisie dziesiętnym występują dokładnie trzy cyfry 1 i dokładnie dwie cyfry 2.

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 6 — maturalne.

Ile jest wszystkich dwucyfrowych liczb naturalnych utworzonych z cyfr: 1, 3, 5, 7, 9, w których cyfry się nie powtarzają?

A. 10

B. 15

C. 20

D. 25

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 7 — maturalne.

Ile jest wszystkich liczb naturalnych czterocyfrowych mniejszych niż 2018 i podzielnych przez 5?

  1. 402
  2. 403
  3. 203
  4. 204

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 8 — maturalne.

Oblicz, ile jest liczb sześciocyfrowych, w których zapisie nie występuje zero, natomiast występują dwie dziewiątki, jedna szóstka i suma wszystkich cyfr jest równa 30.

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 9 — maturalne.

Na ile sposobów można wybrać dwóch graczy spośród 10 zawodników?

A. 100

B. 90

C. 45

D. 20

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 10 — maturalne.

Rozpatrujemy wszystkie liczby naturalne dziesięciocyfrowe, w zapisie których mogą występować wyłącznie cyfry 1, 2, 3, przy czym cyfra 1 występuje dokładnie trzy razy. Uzasadnij, że takich liczb jest 15 360.

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 11.

Komputer jest zabezpieczony hasłem, które składa się z ośmiu znaków i w jego skład może wchodzić każda z 10 cyfr, 32 liter alfabetu (mała i duża) oraz 26 znaków specjalnych? Ile może trwać łamanie hasła poprzez manualne wpisywanie kolejnych możliwych haseł, jeśli jedno hasło wpisujemy 1 s?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 12.

W wyścigu bierze udział 10 koni. Zakład polega na właściwym wytypowaniu kolejności pierwszych trzech koni na mecie. Ile jest różnych możliwych zakładów przy założeniu, że konie nie przybiegają na metę jednocześnie?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 13.

Ile liczb pięciocyfrowych o różnych cyfrach można utworzyć z cyfr \(1,2,3,4,5\)?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 14.

a) Ile można utworzyć liczb z cyfr \(1, 2, 3, 4\), używając każdej z cyfr tylko raz?

b) Ile liczb co najwyżej czterocyfrowych można utworzyć z cyfr \(1, 2, 3, 4\)?

c) Ile liczb czterocyfrowych można utworzyć z cyfr \(0, 1, 2, 3\)?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 15.

Rozwiązać równanie \(C_{x+2}^{2}=1\).

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 16.

W trzech stosach znajdują się karteczki z obrazkami. W pierwszym stosie znajduje się 10 obrazków głów, w drugim — 20 obrazków tułowia, w trzecim — 10 obrazków ilustrujących odnóża. Losujemy jedną kartkę z głową, dwie z tułowiem i jedną z kończynami dolnymi. Układamy kartki, jedną pod drugą, tworząc obrazek stworka. Ile różnych stworków możemy w ten sposób utworzyć?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 17.

Na ile sposobów można wybrać trzyosobową delegację złożoną z co najmniej dwóch chłopców z klasy liczącej 16 chłopców i 14 dziewcząt?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 18.

Na ile sposobów można wybrać trzyosobową delegację złożoną z jednej dziewczyny i dwóch chłopców z klasy liczącej 15 chłopców i 15 dziewcząt?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 19.

Na ile sposobów można wybrać pięcioosobową delegację z klasy liczącej 30 uczniów?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 20.

Ile przekątnych znajduje się w wielokącie foremnym o \(n\) bokach?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 21.

Ile dróg trzeba zbudować, aby połączyć ze sobą dziesięć miejscowości, każda z każdą?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 22.

Malarz chce namalować tęcze z wykorzystaniem wszystkich możliwych konfiguracji kolejności występowania jej siedmiu podstawowych kolorów. Ile tęcz malarz musi namalować?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 23.

Z ilu elementów składa się zbiór \(A\), jeżeli liczba jego permutacji jest 20 razy mniejsza od liczby permutacji tego samego zbioru uzupełnionego o dwa dodatkowe elementy?

Pokaż rozwiązanie zadania.

zadanie maturalne

Zadanie nr 24.

W wyścigu chartów bierze udział sześć psów. Zakład polega na wytypowaniu właściwej kolejności psów na mecie (przy założeniu, że wszystkie dobiegają do mety i nie ma remisu). Ile zakładów trzeba zawrzeć, aby mieć pewność wygranej?

Pokaż rozwiązanie zadania.




Dlaczego garnki są okrągłe?
Co sprawia, że widujemy w sprzedaży garnki o podstawie koła, a nie na przykład kwadratu? Może to zwykłe przyzwyczajenie i wygoda? Okazuje się, że powodów jest kilka.

Inne zagadnienia z tej lekcji


© medianauka.pl, 2009-08-23, A-303
Data aktualizacji artykułu: 2023-07-23



©® Media Nauka 2008-2023 r.