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
A. 100
B. 99
C. 90
D. 19

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?

Zadanie 18.

Na ile sposobów można wybrać dwóch graczy spośród 10 zawodników?
A. 100
B. 90
C. 45
D. 20

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! = 4! - 2! ⋅ 3! = 24 - 2 ⋅ 6 = 24 - 12 = 12
  • 5! - 2! ⋅ 4! = 5! - 2! ⋅ 4! = 120 - 2 ⋅ 24 = 120 - 48 = 72

  • W tym przykładzie występują już trochę większe liczby, zatem nie opłaca się liczyć ile dokładnie wynosi np. 10!. Łatwiej będzie skrócić wspólne czynniki z licznika i mianownika.
    Zauważmy najpierw, że:

    Zatem:

  • W tym przykładzie skrócimy wspólne czynniki z licznika oraz mianownika.
    Zauważmy najpierw, że:

    Zatem:


  • Podobnie jak w przykładach poprzednich - skrócimy wspólne czynniki z licznika i mianownika.
    Zauważmy najpierw, że:

    Zatem podstawiamy i skracamy:


  • W tym przykładzie również skrócimy wspólne czynniki z licznika i mianownika. Wcześniej będziemy musieli jednak "sprowadzić" wszystkie silnie do najmniejszej, czyli do 8!.
    Zauważmy, że:

    W związku z tym podstawiamy i skracamy:

Zadanie 2. Doprowadź do najprostszej postaci:

  • W tym zadaniu (podobnie jak w zadaniu poprzednim) skrócimy wspólne czynniki z licznika i mianownika. Na początku będziemy musieli jednak tak zapisać wyrażenie n!, aby pojawił się wspólny czynnik na górze i na dole ułamka.
    Zauważmy najpierw, że w n! siedzi ukryta (n-1)!:

    Zatem podstawiamy i skracamy:


  • Liczba n! występująca w liczniku ułamka jest większa od liczby (n - 3)! występującej w mianowniku ułamka. Chcąc uzyskać wspólny czynnik w liczniku i mianowniku (aby go potem skrócić) przedstawimy większą z tych liczb jako mniejsza razy coś. Liczbę n! możemy zapisać np. tak:

    Teraz możemy już podstawić i skrócić ułamek:

  • Tutaj postępujemy dokładnie tak samo jak w poprzednim przykładzie. Na początku zauważamy, że:

    Zatem:

  • Zauważmy, że wyrażenie z mianownika możemy zapisać tak:

    Dzięki takiemu przekształceniu uzyskamy wspólny czynnik w liczniku oraz w mianowniku ułamka i będziemy mogli go skrócić:

    Tego typu "sztuczkę" bardzo często wykorzystuje się przy skracaniu ułamków z silnią. Wystarczy jedynie zapamiętać, że zawsze w większej liczbie szukamy wspólnego czynnika dla mniejszej.

  • Liczba w liczniku jest większa, więc zapiszemy ją tak aby pojawił się czynnik z mianownika:

    Dzięki takiemu zapisaniu uzyskamy wspólny czynnik w liczniku i w mianowniku ułamka. Teraz będziemy mogli go skrócić:


  • Liczba w mianowniku jest większa, więc zapiszemy ją tak aby pojawił się czynnik z licznika:

    Dzięki takiemu zapisaniu mianownika uzyskamy wspólny czynnik w liczniku i w mianowniku ułamka. Teraz będziemy mogli go skrócić:

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.