Reguła mnożenia i reguła dodawania - na ile sposobów? Przykłady

Klasa 3 liceum i technikum

Reguła mnożenia mówi, że jeśli wybór składa się z kolejnych etapów, a w każdym etapie liczba możliwości nie zależy od tego, co wybrano wcześniej, to liczba wszystkich wyników jest iloczynem liczb możliwości w poszczególnych etapach. Reguła dodawania mówi, że jeśli wyniki dzielą się na przypadki, które się nie pokrywają, to liczba wszystkich wyników jest sumą liczb wyników w poszczególnych przypadkach. Z tych dwóch reguł wyprowadzimy w kolejnych lekcjach wszystkie wzory kombinatoryki.

Krótko: „i” oznacza mnożenie, „lub” oznacza dodawanie. Wybieramy zupę i drugie danie - mnożymy. Liczba jest dwucyfrowa lub trzycyfrowa - dodajemy.

Reguła mnożenia i drzewo możliwości

Przykład 1. W stołówce są $3$ zupy: pomidorowa (P), rosół (R) i żurek (Ż), oraz $2$ drugie dania: kotlet (K) i naleśniki (N). Obiad to jedna zupa i jedno drugie danie. Ile jest różnych obiadów?

Narysujmy wszystkie możliwości jako drzewo: z punktu startowego wychodzą trzy gałęzie (wybór zupy), a z każdej z nich - dwie kolejne (wybór drugiego dania).

Liście drzewa to wszystkie obiady. Nie trzeba ich liczyć po kolei: z każdej z $3$ zup wychodzą po $2$ gałęzie, więc

$3 \cdot 2 = 6.$

Odpowiedź: jest $6$ różnych obiadów.

Drzewo jest dobre do zrozumienia reguły i do sprawdzenia małych przykładów. Przy większych liczbach rysowanie staje się niemożliwe (kod PIN to $10\,000$ liści), ale rachunek zostaje ten sam: mnożymy liczby gałęzi na kolejnych poziomach.

Reguła mnożenia w zadaniach o liczbach

Typowe zadania maturalne pytają o liczby o określonych cyfrach. Każda cyfra to osobny etap wyboru, a zero nie może stać na początku.

Przykład 2. Ile jest liczb naturalnych czterocyfrowych?

Cyfrę tysięcy wybieramy spośród $1, 2, \ldots, 9$ ($9$ możliwości), każdą z pozostałych trzech cyfr spośród $0, 1, \ldots, 9$ ($10$ możliwości):

$9 \cdot 10 \cdot 10 \cdot 10 = 9000.$

Sprawdzenie: liczby czterocyfrowe to $1000, 1001, \ldots, 9999$, czyli $9999 - 999 = 9000$ liczb.

Przykład 3. Ile jest liczb trzycyfrowych, których wszystkie cyfry są parzyste?

Cyfry parzyste to $0, 2, 4, 6, 8$. Cyfra setek nie może być zerem, więc ma $4$ możliwości, a cyfry dziesiątek i jedności - po $5$:

$4 \cdot 5 \cdot 5 = 100.$

Przykład 4 (zaczynamy od miejsca z ograniczeniem). Ile jest liczb trzycyfrowych nieparzystych, w których wszystkie cyfry są różne?

Krok 1. Cyfra jedności. Liczba jest nieparzysta, gdy kończy się cyfrą $1, 3, 5, 7$ lub $9$ - $5$ możliwości.

Krok 2. Cyfra setek. Nie może być zerem ani cyfrą jedności: z $9$ cyfr niezerowych odpada jedna (cyfra jedności jest nieparzysta, więc na pewno niezerowa) - $8$ możliwości.

Krok 3. Cyfra dziesiątek. Dowolna z $10$ cyfr oprócz dwóch już użytych - $8$ możliwości.

$5 \cdot 8 \cdot 8 = 320.$

Odpowiedź: jest $320$ takich liczb.

Dlaczego zaczęliśmy od cyfry jedności, a nie od setek? Gdybyśmy najpierw wybrali cyfrę setek, liczba możliwości dla cyfry jedności zależałaby od tego, czy cyfra setek była nieparzysta (wtedy zostają $4$ cyfry nieparzyste), czy parzysta (zostaje $5$). Reguła mnożenia wymaga, żeby liczba możliwości w każdym etapie była stała - stąd zasada: najpierw wybieramy to, co ma najwięcej ograniczeń. Gdy to nie wystarcza, dzielimy zadanie na przypadki (reguła dodawania).

Reguła dodawania - rozłączne przypadki

Przykład 5. Ile jest liczb naturalnych mniejszych od $1000$, w których zapisie występują wyłącznie cyfry $1$, $2$ i $3$ (cyfry mogą się powtarzać)?

Takie liczby mogą być jedno-, dwu- albo trzycyfrowe. Te trzy przypadki się nie pokrywają, więc liczymy każdy osobno (regułą mnożenia) i dodajemy:

Uwaga na przypadki, które się pokrywają. Ile jest liczb dwucyfrowych, które zaczynają się cyfrą $5$ lub kończą cyfrą $5$? Zaczynających się od $5$ jest $10$ ($50, \ldots, 59$), kończących się na $5$ jest $9$ ($15, 25, \ldots, 95$). Ale liczba $55$ należy do obu grup, więc zwykłe dodawanie policzyłoby ją dwa razy:

$10 + 9 - 1 = 18.$

Reguła dodawania w czystej postaci działa tylko dla przypadków rozłącznych. Gdy się pokrywają, część wspólną odejmujemy - to zasada włączeń i wyłączeń.

Zdarzenie przeciwne: „co najmniej jeden”

Przykład 6. Ile jest liczb trzycyfrowych, w których co najmniej dwie cyfry są takie same?

Wprost trzeba by rozpatrzyć kilka przypadków (dwie pierwsze cyfry równe, dwie ostatnie, pierwsza i ostatnia, wszystkie trzy). Prościej policzyć liczby, które warunku nie spełniają, czyli liczby o różnych cyfrach, i odjąć je od wszystkich.

Krok 1. Wszystkie liczby trzycyfrowe: $9 \cdot 10 \cdot 10 = 900$.

Krok 2. Liczby o różnych cyfrach: setki $9$ możliwości (bez zera), dziesiątki $9$ (bez cyfry setek, ale zero już wolno), jedności $8$:

$9 \cdot 9 \cdot 8 = 648.$

Krok 3. Odejmujemy: $900 - 648 = 252$.

Odpowiedź: jest $252$ takich liczb.

Sygnałem do liczenia przez dopełnienie są słowa „co najmniej jeden”, „co najmniej dwa takie same”, „nie wszystkie” - przeciwieństwo takiego warunku jest zwykle jednym prostym przypadkiem.

Typowe błędy

• Dodawanie zamiast mnożenia. Zupę i drugie danie wybieramy jednocześnie - to $3 \cdot 2$, a nie $3 + 2$. Dodajemy tylko wtedy, gdy wybieramy jedną z kilku rozłącznych możliwości.
• Zero na początku liczby. Liczb trzycyfrowych jest $900$, a nie $1000$ - pierwsza cyfra ma $9$ możliwości.
• Zła kolejność etapów. Jeśli liczba możliwości w jakimś etapie zależy od wcześniejszego wyboru, zmień kolejność (zacznij od miejsca z ograniczeniem) albo rozbij zadanie na przypadki.
• Dodawanie przypadków, które się pokrywają. Zanim dodasz, sprawdź, czy żaden wynik nie należy do dwóch przypadków naraz.

Najczęstsze pytania

Na czym polega reguła mnożenia w kombinatoryce? Jeśli wybór przebiega w kilku etapach, a w każdym etapie liczba możliwości nie zależy od wcześniejszych wyborów, to liczbę wszystkich wyników otrzymujemy, mnożąc liczby możliwości w kolejnych etapach. Np. $3$ zupy i $2$ drugie dania dają $3 \cdot 2 = 6$ obiadów.

Kiedy stosować regułę mnożenia, a kiedy regułę dodawania? Mnożymy, gdy wybieramy jedną rzecz i drugą (etapy następują po sobie). Dodajemy, gdy wynik należy do jednego lub drugiego z rozłącznych przypadków (np. liczba jest dwucyfrowa lub trzycyfrowa). W wielu zadaniach używa się obu reguł: każdy przypadek liczymy mnożeniem, a wyniki przypadków dodajemy.

Co to jest drzewo w kombinatoryce? To rysunek wszystkich możliwości: z każdego punktu wychodzi tyle gałęzi, ile jest możliwości w danym etapie, a końce gałęzi (liście) to wszystkie wyniki. Liczba liści jest iloczynem liczb gałęzi na kolejnych poziomach - dlatego drzewo dobrze ilustruje regułę mnożenia.

Ile jest liczb czterocyfrowych? Jest ich $9000$: cyfra tysięcy na $9$ sposobów (bez zera), pozostałe trzy cyfry na $10$ sposobów każda, czyli $9 \cdot 10^3 = 9000$.

Ile jest liczb trzycyfrowych o różnych cyfrach?$9 \cdot 9 \cdot 8 = 648$. Cyfra setek - $9$ możliwości (bez zera), dziesiątek - $9$ (bez cyfry setek, zero dozwolone), jedności - $8$ (bez dwóch użytych cyfr).

Kiedy liczyć przez zdarzenie przeciwne? Gdy w treści pojawia się „co najmniej jeden”, „co najmniej dwa takie same” albo „nie wszystkie”. Liczymy wszystkie możliwości i odejmujemy te, które warunku nie spełniają - zwykle jest to jeden prosty przypadek zamiast kilku trudnych.

Przećwicz

• Reguła mnożenia i dodawania - zadania → - stroje, kody, liczby o różnych cyfrach, parzyste i podzielne przez 5, przypadki łączone regułą dodawania (zadania z pełnym rozwiązaniem krok po kroku).
• Cały zestaw: kombinatoryka - zadania z rozwiązaniami →

Podsumowanie

• Wybór w etapach: liczby możliwości w kolejnych etapach mnożymy (reguła mnożenia).
• Rozłączne przypadki: liczby wyników w przypadkach dodajemy (reguła dodawania); gdy przypadki się pokrywają, część wspólną odejmujemy.
• Drzewo możliwości ilustruje regułę mnożenia: liczba liści = iloczyn liczb gałęzi.
• Zaczynamy od etapu z największymi ograniczeniami (np. pierwsza cyfra liczby, cyfra jedności przy parzystości).
• „Co najmniej jeden” liczymy przez zdarzenie przeciwne: wszystkie minus niepasujące.

Zobacz też

• Wariacje - następna lekcja: reguła mnożenia zamieniona we wzór dla ciągów z powtórzeniami i bez.
• Kombinatoryka - permutacje, wariacje, kombinacje - zestawienie wszystkich wzorów na jednej stronie.
• Zasada szufladkowa Dirichleta - inne proste, a mocne narzędzie liczenia.