Kombinatoryka

1 Reguła mnożenia i dodawania

Reguła mnożenia. Jeśli wybór robimy w kilku etapach (i to, i to) – w pierwszym etapie mamy m możliwości, a w drugim n możliwości – to wszystkich wyborów jest

Przykład: w stołówce są 3 zupy i 2 drugie dania. Obiad to zupa i drugie danie. Każda gałąź drzewka to jeden obiad:

Reguła dodawania. Jeśli wybieramy albo z jednej grupy, albo z drugiej (grupy nie mają wspólnych elementów), to liczby możliwości dodajemy. Deser to 4 rodzaje lodów albo 3 ciasta:

Jak rozpoznać? „i”, „najpierw…, potem…” → mnożymy. „albo”, „lub”, rozbicie na przypadki → dodajemy. W wielu zadaniach potrzebne są obie reguły naraz.

2 Liczby o zadanych cyfrach

Liczbę wielocyfrową traktujemy jak rząd kratek – w każdą wpisujemy liczbę możliwych cyfr i mnożymy. Pamiętaj o trzech rzeczach:

• Pierwsza cyfra nie może być zerem – „0 4 7” to nie jest liczba trzycyfrowa.
• Cyfry mogą się powtarzać → w każdej kratce tyle samo cyfr. Cyfry różne → w każdej kolejnej kratce o jedną mniej.
• Najpierw kratki z warunkami: ostatnia cyfra (parzysta: 0, 2, 4, 6, 8; podzielna przez 5: 0 lub 5), potem pierwsza (bez zera), a dopiero na końcu pozostałe.

Wszystkich liczb trzycyfrowych jest

Liczb trzycyfrowych o różnych cyfrach jest (pierwsza: 9 cyfr bez zera, druga: 10 − 1 = 9, bo zero już wolno, trzecia: 8)

Liczb trzycyfrowych podzielnych przez 5 (cyfry mogą się powtarzać, ostatnia to 0 lub 5) jest

Uwaga na egzaminie: gdy cyfry mają być różne, a ostatnia może być zerem (liczby parzyste, podzielne przez 5), zero „psuje” liczenie pierwszej kratki. Wtedy rozbij zadanie na dwa przypadki: ostatnia cyfra to 0 albo nie – i dodaj wyniki.

3 Ile liczb? – pobaw się

Ustaw warunki, a zobaczysz kratki z liczbą możliwości. Znaczek krok pokazuje, w jakiej kolejności warto wypełniać kratki – kratki z warunkami są obwiedzione na pomarańczowo.

4 Ustawienia: n!

Na ile sposobów można ustawić n różnych osób (przedmiotów) w rzędzie? Na pierwsze miejsce mamy n kandydatów, na drugie n − 1, …, na ostatnie 1. Ten iloczyn to n silnia:

Warto pamiętać kilka pierwszych wartości:

Każde takie ustawienie to permutacja. Umownie 0! = 1.

Warunek „obok siebie”: „sklej” te osoby w jeden blok, ustaw bloki, a potem pomnóż przez liczbę ustawień wewnątrz bloku. „Nie obok siebie” – od wszystkich ustawień odejmij te, w których stoją obok siebie.

5 Wybór bez kolejności

Czasem kolejność ma znaczenie (przewodniczący i zastępca), a czasem nie (dwuosobowa delegacja). W klasie 20 uczniów przewodniczącego i zastępcę wybieramy na

ale dwuosobową delegację tylko na połowę tej liczby, bo para „Ola i Kuba” to ta sama para co „Kuba i Ola”:

Liczbę sposobów wyboru k elementów z n (bez kolejności) oznaczamy symbolem Newtona (czytamy „n po k”):

W praktyce najczęściej wystarczy wybór dwóch elementów:

Na przykład 10 osób wita się, każdy z każdym jednym uściskiem dłoni. Każda osoba ściska 9 dłoni, ale wtedy każdy uścisk liczymy dwa razy:

Na egzaminie: zapytaj siebie, czy zamiana kolejności daje inny wynik. Tak (miejsca, funkcje, cyfry w liczbie) → mnożymy kolejne możliwości. Nie (grupa, delegacja, para, uścisk) → dzielimy przez liczbę kolejności, czyli liczymy „n po k”.

6 „Co najmniej jeden” i typowe błędy

Gdy w treści pada „co najmniej jeden”, zwykle łatwiej policzyć przeciwieństwo („ani jednego”) i odjąć je od wszystkich możliwości:

Ile liczb trzycyfrowych ma co najmniej jedną cyfrę 7? Wszystkich liczb trzycyfrowych jest

Liczb bez siódemki: pierwsza cyfra – bez 0 i bez 7, czyli 8 możliwości, pozostałe – bez 7, czyli po 9 możliwości:

Zatem liczb z co najmniej jedną siódemką jest

Typowe błędy

• Zero na początku. Pierwsza kratka ma 9 możliwości (1–9), a nie 10.
• Brak podziału na przypadki. Liczby parzyste o różnych cyfrach to nie „4 · 8 · …” ani „5 · 9 · …” – zero na końcu trzeba rozpatrzyć osobno (przykład 1).
• Dodawanie zamiast mnożenia. Wybór „zupa i drugie danie” to 3 · 2, nie 3 + 2.
• Kolejność tam, gdzie jej nie ma. Uściski dłoni, pary i delegacje liczone jako 10 · 9 są policzone podwójnie – trzeba podzielić przez 2.
• „Co najmniej jeden” liczone wprost. Łatwo policzyć coś dwa razy (np. liczbę 777) – bezpieczniej odjąć od wszystkich przypadki „żaden”.

7 Sprawdź się