1. Wprowadzenie do kombinatoryki

Kombinatoryka jest działem matematyki, który pomaga odpowiedzieć na pytania typu: "ile jest możliwych wyników w rzucie monetą?", "Na ile sposobów możemy wybrać delegację dwuosobową z klasy 28 osobowej?", itp.
Aby rozwiązać tego typu zadania, często stosuje się wzory na permutacje, kombinacje, wariacje oraz wariacje z powtórzeniami. Na szczęście nie trzeba pamiętać tych wszystkich wzorów, aby szybko i skutecznie rozwiązywać zadania z kombinatoryki. Do rozwiązania większości zadań w zupełności wystarcza reguła mnożenia i wzór na kombinację.

2. Reguła mnożenia

Regułę mnożenia przeanalizujemy na poniższym przykładzie.
Przykład 1. Rzucamy trzy razy monetą. Ile jest wszystkich możliwych wyników tego doświadczenia?
Rozwiązanie
Możliwe wyniki to np.: (Orzeł,Orzeł,Reszka), (O,R,R), (R,O,R), (R,R,R)...
Zatem:
W I rzucie może wypaść orzeł lub reszka, czyli są 2 możliwości.
W II rzucie również może wypaść orzeł lub reszka, czyli są 2 możliwości.
W III rzucie również może wypaść orzeł lub reszka, czyli są 2 możliwości.
Powiemy: w I rzucie są 2 możliwości i w II rzucie są 2 możliwości i w III rzucie są 2 możliwości
Reguła mnożenia mówi, że w takiej sytuacji mamy: 2*2*2=8 możliwości.
Czyli zamieniamy po prostu spójnik "i" na mnożenie.

Reguła mnożenia przydaje się podczas rozwiązywania wielu zadań z kombinatoryki. Poniżej znajduje się kilka zadań na zastosowanie tej reguły.

Zadanie 1.

Rzucamy 10 razy monetą. Ile jest możliwych wyników?
Rozwiązanie PDF

Zadanie 2.

Rzucamy 3 razy sześcienną kostką do gry. Ile jest możliwych wyników?
Rozwiązanie PDF

Zadanie 3.

Rzucamy 5 razy sześcienną kostką do gry. Ile jest możliwych wyników?
Rozwiązanie PDF

Zadanie 4.

Ile jest wszystkich liczb trzycyfrowych?
Rozwiązanie PDF

Zadanie 5.

Ze wsi A do wsi B prowadzi 5 ścieżek przez las. Na ile sposobów można odbyć spacer A-B-A tak, aby spacer ze wsi B do wsi A odbyć inną ścieżką niż ze wsi A do wsi B?

Zadanie 6.

Na rysunku dany jest kwadrat, trójkąt i elipsa. Mamy również do dyspozycji 8 kolorów farb. Na ile różnych sposobów można pomalować wszystkie trzy figury tymi ośmioma kolorami, tak aby każda figura była w innym kolorze?

Zadanie 7.

Flagę, taką jak pokazano na rysunku, należy zszyć z trzech jednakowej szerokości pasów kolorowej tkaniny. Oba pasy zewnętrzne mają być tego samego koloru, a pas znajdujący się między nimi ma być innego koloru. Liczba różnych takich flag, które można uszyć, mając do dyspozycji tkaniny w 10 kolorach, jest równa

Zadanie 8.

Wszystkich liczb naturalnych dwucyfrowych, których obie cyfry są mniejsze od 5 jest

Zadanie 9.

Liczba sposobów, na jakie Ala i Bartek mogą usiąść na dwóch spośród pięciu miejsc w kinie, jest równa

Zadanie 10.

Ile jest liczb naturalnych czterocyfrowych takich, że w ich zapisie dziesiętnym występuje jedna cyfra nieparzysta i trzy cyfry parzyste.

Zadanie 11.

Ile jest liczb naturalnych dwucyfrowych podzielnych przez 15 lub 20?

Zadanie 12.

Ile jest liczb naturalnych trzycyfrowych, w których cyfra dziesiątek jest o 2 większa od cyfry jedności?

Zadanie 13.

Ile jest wszystkich liczb naturalnych dwucyfrowych, w których obie cyfry są parzyste?

Zadanie 14.

Ile jest wszystkich liczb naturalnych dwucyfrowych, w których obie cyfry są nieparzyste?

Zadanie 15.

Ile jest wszystkich liczb naturalnych trzycyfrowych, w których wszystkie trzy cyfry są parzyste?

Zadanie 16.

Wszystkich dodatnich liczb całkowitych czterocyfrowych mniejszych od 4000, zapisanych za pomocą cyfr: 3, 5, 7, 9 tak, że żadna cyfra się nie powtarza, jest

Zadanie 17.

Ile jest wszystkich liczb naturalnych trzycyfrowych podzielnych przez 5?

3.1. Definicja silni i przykłady

Zacznijmy od podania definicji silni.
Definicja Silnia liczby naturalnej n - to iloczyn kolejnych liczb naturalnych od 1 do n.
Silnię liczby naturalnej n oznaczamy symbolem n! (czytamy en silnia).
Mamy zatem:
n! = 1 ⋅ 2 ⋅ 3 ⋅ ... ⋅ (n - 1) ⋅ n
Przykłady
  • 3! = 1 ⋅ 2 ⋅ 3 = 6
  • 4! = 1 ⋅ 2 ⋅ 3 ⋅ 4 = 24
  • 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120
  • 6! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 = 720
  • 10! = 1 ⋅ 2 ⋅ 3 ... ⋅ 9 ⋅ 10 = 3628800
  • 17! = 1 ⋅ 2 ⋅ 3 ... ⋅ 16 ⋅ 17 = 355687428096000
Silnię z dowolnej liczby naturalnej możesz obliczyć przy pomocy poniższego programu.
Po co jest ta silnia?
Symbol silni pozwala w prosty i krótki sposób zapisywać długie iloczyny liczb.
Jak widać na powyższym przykładzie - już dla liczby 17! jej zapis w systemie dziesiętnym składa się aż z 15 cyfr. Okazuje się, że liczba 100! zapisana w systemie dziesiętnym składa się już ze 157 cyfr!
Nikt normalny nie chciałby na pewno zapisać w ten sposób tak dużych liczb.
Zapisanie liczby przy wykorzystaniu silni jest korzystne również dlatego, że daje nam informację z jakich czynników składa się dana liczba. Znajomość takiego rozkładu jest szczególnie przydatna przy skracaniu ułamków (gdy w liczniku i mianowniku ułamka występują silnie).

3.2. Program do liczenia silni

Podaj liczbę naturalną n dla której chcesz obliczyć n!:
n =

3.3. Zadania z silni

Zadanie 1. Oblicz:
  • 4! - 2! ⋅ 3!
    Rozwiązanie
  • 5! - 2! ⋅ 4!
    Rozwiązanie

  • Rozwiązanie

  • Rozwiązanie

  • Rozwiązanie

  • Rozwiązanie
Zadanie 2. Doprowadź do najprostszej postaci:

  • Rozwiązanie

  • Rozwiązanie

  • Rozwiązanie

  • Rozwiązanie

  • Rozwiązanie

  • Rozwiązanie

4. Kombinacja

Kombinacja pozwala policzyć na ile sposobów można wybrać k elementów z n elementowego zbioru.
Wzór na kombinację jest następujący: wzór na kombinację
Kombinację zapisujemy krótko za pomocą Symbolu Newtona: wzór na symbol Newtona
Przykłady
  • Na ile sposobów można wybrać 2 osoby w klasie 30 osobowej?
    Rozwiązanie symbol Newtona '30 nad 2'
    Odpowiedź: Dwie osoby można wybrać w klasie 30 osobowej na 435 sposobów.
  • Na ile sposobów można wybrać 3 zawodników w drużynie 12 osobowej?
    Rozwiązanie symbol Newtona '12 nad 3'
    Odpowiedź: Trzech zawodników w drużynie 12 osobowej można wybrać na 220 sposobów.

Zadanie 1.

Na jednej prostej zaznaczono 3 punkty, a na drugiej 4 punkty. Ile jest wszystkich trójkątów, których wierzchołkami są trzy spośród zaznaczonych punktów?

Zadanie 2.

Dane są dwa pojemniki. W pierwszym z nich znajduje się 9 kul: 4 białe, 3 czarne i 2 zielone. W drugim pojemniku jest 6 kul: 2 białe, 3 czarne i 1 zielona. Z każdego pojemnika losujemy po jednej kuli. Oblicz prawdopodobieństwo wylosowania dwóch kul tego samego koloru.

Zadanie 3.

Dane są dwa pojemniki. W pierwszym z nich znajduje się 9 kul: 4 białe, 3 czarne i 2 zielone. W drugim pojemniku jest 6 kul: 2 białe, 3 czarne i 1 zielona. Z każdego pojemnika losujemy po jednej kuli. Oblicz prawdopodobieństwo wylosowania dwóch kul różnych kolorów.

Zadanie 4.

Dane są dwa pojemniki. W pierwszym z nich znajduje się 11 kul: 7 białych i 4 czarne. W drugim pojemniku jest 6 kul: 3 białe i 3 czarne. Z każdego pojemnika losujemy po dwie kule. Oblicz prawdopodobieństwo wylosowania czterech kul czarnych.

5. Permutacja

Permutacja polega na przestawianiu elementów w zbiorze.
Jeżeli mamy zbiór składający się z 3 elementów, np. {A, B, C} to jego permutacjami są:
ABC, ACB, BAC, BCA, CAB, CBA
Zatem mamy 6 permutacji zbioru 3-elementowego. Aby policzyć liczbę permutacji dowolnego zbioru n-elementowego zastosujemy wzór: wzór na permutację
Przykłady
  • Na ile sposobów można ustawić 5 osób w kolejce?
    Rozwiązanie 5!=1*2*3*4*5=120 Odpowiedź: Pięć osób można ustawić w kolejce na 120 sposobów.
  • Ile liczb można utworzyć z cyfr: 1, 2, 3, 4, 5, 6, 7? (każdą cyfrę trzeba wykorzystać dokładnie 1 raz)
    Rozwiązanie
    Podane cyfry mogą być ustawione w dowolnej kolejności. Mamy zatem permutację zbioru 7-elementowego. 7!=1*2*3*4*5*6*7=5040 Odpowiedź: Możemy utworzyć 5040 liczb.
  • Na ile sposobów można ustawić na półce 7 książek formatu A-5 oraz 6 książek formatu A-4, aby nie rozdzielić ich wymiarowo?
    Rozwiązanie
    Książki formatu A-5 muszą stać obok siebie, ale możemy ustawić je na 7! sposobów.
    Podobnie - książki formatu A-4 muszą stać obok siebie, ale mogą być postawione na 6! sposobów.
    Wszystkie książki na półce możemy jednak ustawić na 2 sposoby - albo od większych do mniejszych, albo od mniejszych do większych. Zatem wszystkich możliwości mamy: 2*7!*6! Odpowiedź: Książki możemy ustawić na 2 · 7! · 6! sposobów.

6. Wariacja z powtórzeniami

Przyjmijmy, że mamy dany zbiór elementów (np. zbiór liter). Wariacja z powtórzeniami pozwala na utworzenie ciągu z elementów tego zbioru, z tym, że dopuszcza powtarzanie elementów. Wzór na wariację z powtórzeniami jest następujący: wzór na wariację z potórzeniami Przykłady
  • Ile słów pięcioliterowych (nawet tych bezsensownych) można utworzyć z liter {A, B, C}?
    Rozwiązanie:
    Przykładami taki słów są: "AAAAA", "AABCA", "CBCBB". Na każde z 5 miejsc możemy wybrać jedną z 3 liter, zatem wszystkich możliwości mamy: 3^5 = 243 Odpowiedź: Można utworzyć 243 wyrazy.
  • Ile słów dwuliterowych (nawet tych bezsensownych) można utworzyć z liter {A, B, C, D}?
    Rozwiązanie:
    Przykładami taki słów są: "AA", "DC", "CD". Na każde z 2 miejsc możemy wybrać jedną z 4 liter, zatem wszystkich możliwości mamy: 4^2 = 16 Odpowiedź: Można utworzyć 16 wyrazów.

7. Wariacja bez powtórzeń

Przyjmijmy, że mamy dany zbiór elementów (np. zbiór liter). Wariacja bez powtórzeń pozwala na utworzenie ciągu z elementów tego zbioru, z tym, że nie dopuszcza powtarzania elementów. Wzór na wariację bez powtórzeń jest następujący: wzór na wariację bez potórzeń Przykłady
  • Ile istnieje czterocyfrowych PIN-kodów składających się z różnych cyfr?
    Rozwiązanie:
    Mamy do dyspozycji 10 cyfr: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Przykładowymi kodami o różnych cyfrach są: 1234, 0189, 9734. Wszystkich takich wariacji bez powtórzeń jest: 10!/6! Odpowiedź: Istnieje 5040 czterocyfrowych kodów o różnych cyfrach.

8. Różne zadania z kombinatoryki

Zadanie 1.

Ile jest liczb naturalnych czterocyfrowych o sumie cyfr równej 2?

Zadanie 2.

Wszystkich liczb naturalnych dwucyfrowych, które są podzielne przez 6 lub przez 10, jest

Zadanie 3.

Cztery dziewczynki i sześciu chłopców siedzą na tym samym pniu zwalonego dębu. Dziewczynki siedzą obok siebie i chłopcy również siedzą obok siebie. Wszystkich możliwych sposobów posadzenia dzieci w ten sposób jest

Zadanie 4.

Oblicz, ile jest liczb naturalnych sześciocyfrowych, w zapisie których występuje dokładnie trzy razy cyfra 0 i dokładnie raz występuje cyfra 5.