ELEMENTY KOMBINATORYKI
1 z 6
ELEMENTY KOMBINATORYKI
Reguła mnożenia
Jeżeli wybór zależy od n decyzji, przy czym na decyzję pierwszą mamy a
1
możliwości, decyzję drugą
- a
2
możliwości, ..., decyzję n-tą mamy a
n
możliwości, to wybór może być dokonany
na a
1
• a
2
•... • a
n
sposobów.
Przykład.1.
Na ile sposobów można obok siebie wstawić 6 płyt CD na półce?
Rozw.
Pierwszą płytę CD możemy ustawić na 6 miejscach. (6 możliwości podjęcia l decyzji)
Drugą płytę CD możemy ustawić na 5 miejscach, ponieważ jedno z miejsc jest już zajęte. (5 możliwości
podjęcia drugiej decyzji)
Trzecią płytę CD można postawić już tylko na 4 miejscach, i tak dalej...
Ponieważ podejmujemy łącznie 6 decyzji, zatem możemy zastosować regułę mnożenia.
65432l = 720
Odp. 6 płyt CD można ustawić na półce na 720 sposobów.
Przykład.2.
Ile można przeprowadzić reakcji chemicznych mając do dyspozycji 5 składników, gdy łączymy ze sobą
po trzy składniki w jednakowych ilościach, jeśli kolejność dokładania składników:
a) odgrywa rolę; b) nie odgrywa roli?
Rozw.
a) Pierwszy składnik wybieramy spośród 5 składników, drugi spośród 4, a trzeci spośród 3. Zatem
wyboru, gdy kolejność ogrywa rolę, możemy dokonać na:
543=60
Odp. Możemy przeprowadzić 60 reakcji chemicznych, wybierając po 3 składniki z 5, gdy kolejność
dokładania składników jest ważna.
b) Przypuśćmy, że składniki to: A, B, C, D, E. Jeżeli kolejność łączenia składników nie odgrywa roli,
to rozwiązanie zadania sprowadza się do znalezienia odpowiedzi na pytanie na ile sposobów,
możemy wybrać trzy składniki spośród 5. Aby rozwiązać ten problem zbudujemy tabelkę:
ELEMENTY KOMBINATORYKI
2 z 6
A
B
C D E
x
x
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
x = oznacza, że wybrano dany składnik
Zatem możemy na 10 sposobów wybrać 3
składniki spośród 5,
Odp. Możemy przeprowadzić 10 reakcji chemicznych, wybierając
po 3 składniki z 5, gdy kolejność dokładania składników nie jest
istotna.
Przykład.3.
W finale zawodów pływackich startuje S zawodników. Ile istnieje możliwości zajęcia
przez nich trzech różnych miejsc na podium?
Rozw.
Ponieważ dla zawodników jest ważne, czy zajmie miejsce pierwsze, drugie, czy trzecie,
więc kolejność jest istotna. Wykluczamy ex equo. Zatem pierwsze miejsce może zająć
każdy z 8 zawodników, drugie każdy z siedmiu, a trzecie każdy z sześciu. Wobec tego
mamy:
8
7
6=336 możliwości zajęcia miejsc na podium.
Przykład.4.
Oblicz, ile jest liczb trzycyfrowych zapisanych za pomocą cyfr l,
3, 4, 5.
Rozw.
decyzją podejmujemy kolejno, dlatego stosujemy regułą mnożenia Odp. Jest 125 liczb trzycyfrowych
zapisanych za pomocą cyfr 1,2,3,4, 5.
Przykład.5.
Oblicz, ile jest liczb trzycyfrowych zapisanych za pomocą cyfr 0, l, 2,3,4.
Rozw.
ELEMENTY KOMBINATORYKI
3 z 6
Jest 100 liczb trzycyfrowych zapisanych za pomocą cyfr 0, l, 2, 3, 4.
Zadania
1. Na ile sposobów można ustawić w kolejce trójkę dziewcząt i dwójkę chłopców? Ile będzie
możliwości, jeżeli dziewczęta mają stać przed chłopcami?
2. Grupa składa się z 4 dziewcząt i 4 chłopców. Na ile sposobów można utworzyć z nich pary
taneczne?
3. Na ile sposobów 20 uczniów klasy może zająć miejsca w sali lekcyjnej, w której jest 30 miejsc?
4. Ile jest możliwości rozdziału 3 medali (złoty, srebrny, brązowy) pomiędzy
5 zawodników?
5. „Milion zestawów obiadowych" głosi reklama restauracji. Zamawiając obiad masz do wyboru l O
przystawek i 15 zup. Drugie danie możesz skomponować mając do wyboru 8 rodzajów mięs, 6
różnych surówek i 10 (na różne sposoby przyrządzonych) ziemniaków. Do pełnego obiadu jest jesz-
cze 12 rodzajów napojów i 5 deserów. Czy reklama restauracji jest prawdziwa?
6. Pewna dzielnica ma 7-cyfrowe numery telefonów zaczynające się od liczby 47. Ile może być
maksymalnie numerów telefonów w tej dzielnicy?
8. Ile może być maksymalnie różnych 4-cyfrowych numerów PIN?
n silnia i symbol Newtona
Na przykład:
2! = 12 = 2,
3! = 123=6
5! = l2345 =120
7! = 1234567 = 6! 7 = 4! 567
Ćw.1. Oblicz:
ELEMENTY KOMBINATORYKI
4 z 6
Ćw.2. Oblicz:
Ćw.3.
Ćw.4.
Permutacje
Jeśli ze zbioru n -elementowego wybieramy elementy w ten sposób, że:
• wybieramy n elementów
• istotna jest kolejność wybierania elementów
to tworzymy ciąg n -elementowy, zwany permutacją tego zbioru.
Przykł.6:
Przestawiając w dowolny sposób litery słowa kos,
tworzymy
nowe słowa (mające sens lub nie). Zilustruj grafem
możliwości tworzenia słów i podaj liczbę wszystkich słów,
które
można w ten sposób otrzymać.
Rozwiązanie.
Wszystkie możliwe ustawienia zbioru liter {k, o, s} można
zapisać w
postaci 3-literowych ciągów, gdzie pierwszą literę można
wybrać na
trzy sposoby, tj. k lub o lub s, drugą literę do każdej z liter
k, o, s
można wybrać na dwa sposoby, a trzecią literę na jeden
sposób.
Zgodnie z regułą mnożenia mamy 3
2
1 , czyli 3 ! wyników (
= 3! ).
Odp.: Można otrzymać 6 różnych słów
ELEMENTY KOMBINATORYKI
5 z 6
DEF:
Permutacją zbioru n-elementowego {a
1
,a
2
,..., a
n
} nazywamy n-wyrazowy ciąg utworzony ze
wszystkich elementów tego zbioru.
Ćw.5.
Zilustruj grafem możliwości wyboru i podaj liczbę wszystkich wyrazów, które można otrzymać,
przestawiając w dowolny sposób litery w wyrazie bal.
Uwaga
• Permutacja to ustawienie wszystkich elementów zbioru w pewnej kolejności.
• Dwie permutacje tego samego zbioru różnią się między sobą co najwyżej kolejnością elementów.
TW: Liczba P
n
wszystkich permutacji zbioru n-elementowego jest równa n! P
n
=n!,
gdzie nϵ N
+
.
Ćw.6.
Oblicz, ile różnych wyrazów (mających sens lub nie) można utworzyć, przestawiając w dowolny sposób litery w
wyrazie: a) FUNKCJA, b) MONETA.
Ćw.7.
Ile liczb pięciocyfrowych można utworzyć z cyfr 0, l, 2, 3, 4, przestawiając je w dowolny sposób?
Ćw.8.
Ile liczb czterocyfrowych parzystych można utworzyć z cyfr l, 3, 4, 5, przestawiając je w dowolny sposób?
Przedstaw doświadczenie losowe w postaci grafu.
Ćw.9.
Czworo przyjaciół - Marta (M), Ewa (E), Radek (R) i Patryk (P) - wybiera się na wycieczkę samochodową. W
samochodzie są dwa siedzenia z przodu i dwa z tyłu. Tylko Marta i Patryk mają prawo jazdy. Na ile różnych
sposobów wycieczkowicze mogą usiąść w samochodzie?
Ćw.10.
Pięcioro uczniów - Agata (A), Bartek (B), Celina (C), Damian (D) i Ewa (E) - ustawiło się jedno za drugim w
kolejce. Oblicz, na ile sposobów:
a) uczniowie mogą stanąć w kolejce,
b) uczniowie mogą stanąć w kolejce tak, że dziewczęta stoją na początku kolejki,
c) uczniowie mogą stanąć w kolejce tak, że między każdymi dwoma dziewczętami stoi chłopiec.
Ćw.11.
Oblicz, ile wyrazów, mających sens lub nie, można utworzyć ze wszystkich liter słowa:
a) PARAWAN, b) MATEMATYKA.
Ćw.12.
Oblicz, ile wyrazów, mających sens lub nie, możesz utworzyć z liter własnego: a) imienia, b) nazwiska.
Przykład.7.:
Oblicz, na ile sposobów trzy koleżanki: Ala (A), Beata (B) i Czesia (C), mogą:
a) stanąć w rzędzie lub usiąść na ławce mieszczącej trzy osoby,
b) usiąść przy okrągłym stole, przy którym stoją trzy ponumerowane krzesła,
ELEMENTY KOMBINATORYKI
6 z 6
c) stanąć w koło i złapać się. za ręce.
Rozw.
Ćw.14
Oblicz, na ile sposobów można posadzić pięć osób na pięciu ponumerowanych krzesłach:
a) ustawionych w rzędzie, b) ustawionych przy okrągłym stole.
Ćw.15.
Oblicz, na ile sposobów można ustawić obok siebie 4 tomy encyklopedii, jeśli:
a) zachowujemy kolejność tomów, b) nie zachowujemy kolejności tomów.
Ćw.16.
Na ile sposobów można ustawić na półce obok siebie sześć różnych książek?
Ćw.17.
Przestawiając w dowolny sposób litery wyrazu SYMBOL, tworzymy nowe wyrazy (mające sens lub
nie). Oblicz, ile otrzymamy wyrazów:
a) które zaczynają się od litery L, b) w których pierwsze trzy litery tworzą sylabę BOL, c) które nie kończą się
literą Y.
Ćw.18.
Liczba permutacji zbioru mającego n + 2 elementy jest 210 razy większa niż liczba permutacji zbioru
n-elementowego. Oblicz n.
Ćw.19.
Oblicz, ile jest liczb czterocyfrowych większych od 3000, które można utworzyć, przestawiając cyfry:
l, 2, 3 i 4.
Ćw.20.
Ile słów, mających sens lub nie, można utworzyć przestawiając litery w wyrazie: a) BARBARA,
b) BARBAKAN?
Ćw.21.
Ile liczb dziewięciocyfrowych można utworzyć z cyfr l, 2, 3, 4, 5, 6, 7, 8, 9, przestawiając je w
dowolny sposób?
Ćw.22. W kolejce do kasy biletowej czeka 5 osób: 2 panie i 3 panów.
a) Na ile sposobów można ustawić w tej kolejce wszystkie 5 osób?
b) Panie mają pierwszeństwo. Na ile sposobów można ustawić kolejkę przy takim założeniu?
Ćw.23. Na ile sposobów można uporządkować zbiór {3,2,4,1}?
Ćw.24. Oblicz, ile jest permutacji otrzymanych z liter wyrazu: a) figura; b) alfabet.
Ćw.25. W gonitwie startuje 8 koni. Interesuje nas kolejność, w jakiej konie miną linię mety. Ile jest możliwych
wyników zakończenia tej gonitwy, gdy wszystkie konie przybędą na metę?
Ćw.26. Klasa liczy 28 uczniów, w tym 12 chłopców. Na ile sposobów można ustawić chłopców tej klasy:
a) w szeregu;
b) w szeregu, w którym Kamil i Bartek stoją obok siebie.
Ćw.27. Na nowo wybudowanym osiedlu jest 5 ulic. Postanowiono, że nazwy tych ulic będą pochodzić od nazw
miesięcy. Analizowano różne możliwe zestawy po pięć nazw miesięcy. Ile jest takich zestawów?