MMatematyka Krok po Kroku ← Wróć do kombinatoryki
Moduł 3 · Wariacje · zakres rozszerzony

Wariacje

Wariacja wybiera część elementów i ustawia je w kolejności. Nauczysz się rozróżniać wariacje bez powtórzeń i z powtórzeniami oraz stosować je w zadaniach o rolach, kodach, liczbach i dodatkowych ograniczeniach.

1

Kiedy stosujemy wariację?

Wariację stosujemy wtedy, gdy z $n$ dostępnych elementów wybieramy $k$ elementów, a ich kolejność ma znaczenie. Wynik można zapisać jako uporządkowany ciąg długości $k$.

Wariacja $k$-elementowa zbioru $n$-elementowego opisuje obsadzenie $k$ rozróżnialnych miejsc elementami wybranymi spośród $n$ dostępnych. Zamiana elementów na dwóch miejscach daje inny wynik.
1. Ile jest miejsc?Ustal liczbę $k$: liczbę ról, pozycji albo znaków kodu.
2. Czy kolejność ma znaczenie?Jeżeli AB i BA oznaczają różne wyniki, pracujesz z uporządkowaniem.
3. Czy wolno powtarzać?Sprawdź, czy ten sam element może zostać użyty na więcej niż jednym miejscu.
Bez powtórzeń$$V_n^k=\frac{n!}{(n-k)!}=n(n-1)\cdots(n-k+1),\qquad 0\leq k\leq n$$
Z powtórzeniami$$\overline{V}_n^k=n^k$$
2

Wariacje bez powtórzeń

Każdy element może zostać wykorzystany najwyżej raz. Na pierwsze miejsce mamy $n$ możliwości, na drugie $n-1$, a na $k$-te $n-k+1$ możliwości.

Przykład rozwiązany krok po kroku

Podium zawodów

Z 8 zawodników przyznajemy złoty, srebrny i brązowy medal. Ile jest możliwych wyników podium?

  1. Obsadzamy $3$ różne miejsca, więc kolejność ma znaczenie.
  2. Jeden zawodnik nie może zdobyć dwóch medali, zatem nie dopuszczamy powtórzeń.
  3. Na kolejne miejsca mamy $8$, $7$ i $6$ kandydatów.
$$V_8^3=8\cdot7\cdot6=336$$

Odpowiedź: istnieje $336$ możliwych wyników podium.

Zadanie 1

Z 10 osób wybieramy przewodniczącego, zastępcę i skarbnika. Jedna osoba może pełnić tylko jedną funkcję. Ile jest możliwości?

Rozwiązanie krok po kroku
  1. Trzy funkcje są różne, więc zamiana osób między funkcjami zmienia wynik.
  2. Nie wolno wybrać tej samej osoby ponownie, dlatego stosujemy wariację bez powtórzeń.
  3. Na kolejne funkcje mamy $10$, $9$ i $8$ możliwości.
  4. $V_{10}^3=10\cdot9\cdot8=720$.
Odpowiedź: funkcje można obsadzić na $720$ sposobów.
3

Wariacje z powtórzeniami

Na każdym z $k$ miejsc można ponownie użyć dowolnego spośród $n$ elementów. Liczba możliwości nie zmniejsza się po obsadzeniu kolejnego miejsca.

Przykład rozwiązany krok po kroku

Czterocyfrowy PIN

Ile jest czterocyfrowych kodów PIN, jeżeli używamy cyfr od $0$ do $9$, a cyfry mogą się powtarzać?

  1. Kod ma $4$ rozróżnialne pozycje.
  2. Na każdej pozycji można wybrać jedną z $10$ cyfr.
  3. Cyfra wykorzystana wcześniej może pojawić się ponownie.
  4. Kod może zaczynać się zerem, ponieważ nie jest liczbą czterocyfrową.
$$\overline{V}_{10}^4=10^4=10000$$

Odpowiedź: istnieje $10000$ kodów PIN, wliczając kod $0000$.

Zadanie 2

Ile pięcioznakowych kodów można zbudować ze znaków A, B, C i D, jeżeli znaki mogą się powtarzać?

Rozwiązanie krok po kroku
  1. Kod ma $5$ pozycji, więc $k=5$.
  2. Na każdej pozycji mamy $4$ możliwości.
  3. Powtórzenia są dozwolone, dlatego każdorazowo pozostają wszystkie $4$ znaki.
  4. $\overline{V}_4^5=4^5=1024$.
Odpowiedź: można zbudować $1024$ kody.
4

Kod a liczba: rola zera na początku

W kodzie zero może zajmować pierwszą pozycję. W zapisie liczby wielocyfrowej pierwsza cyfra nie może być zerem. Dlatego w zadaniach o liczbach często liczymy możliwości na kolejnych miejscach zamiast od razu podstawiać do wzoru.

Przykład rozwiązany krok po kroku

Trzycyfrowe liczby o różnych cyfrach

Ile jest dodatnich liczb trzycyfrowych, których cyfry się nie powtarzają?

  1. Cyfrę setek wybieramy spośród $1,2,\ldots,9$: mamy $9$ możliwości.
  2. Na miejscu dziesiątek wolno użyć zera, ale nie cyfry setek: pozostaje $9$ możliwości.
  3. Na miejscu jedności nie wolno użyć dwóch cyfr wybranych wcześniej: pozostaje $8$ możliwości.
$$9\cdot9\cdot8=648$$

Odpowiedź: istnieje $648$ dodatnich liczb trzycyfrowych o różnych cyfrach.

Zadanie 3

Ile jest dodatnich liczb czterocyfrowych parzystych, których cyfry się nie powtarzają?

Rozwiązanie krok po kroku

Przypadek I: cyfrą jedności jest 0

  1. Cyfrę tysięcy wybieramy na $9$ sposobów.
  2. Na setki pozostaje $8$ cyfr, a na dziesiątki $7$ cyfr.
  3. Otrzymujemy $9\cdot8\cdot7=504$ liczby.

Przypadek II: cyfrą jedności jest 2, 4, 6 albo 8

  1. Cyfrę jedności wybieramy na $4$ sposoby.
  2. Cyfrę tysięcy wybieramy spośród ośmiu niezerowych cyfr różnych od cyfry jedności: $8$ możliwości.
  3. Na setki pozostaje $8$ cyfr, a na dziesiątki $7$.
  4. Otrzymujemy $4\cdot8\cdot8\cdot7=1792$ liczby.
  1. Przypadki są rozłączne, więc ich liczby dodajemy.
  2. $504+1792=2296$.
Odpowiedź: istnieje $2296$ takich liczb.
5

Role i miejsca z dodatkowym warunkiem

Ograniczenie może zmniejszyć liczbę kandydatów na określone miejsce albo wymagać podziału na rozłączne przypadki. W każdym przypadku stosujemy regułę mnożenia, a wyniki przypadków dodajemy.

Przykład rozwiązany krok po kroku

Ewa musi otrzymać jedną z dwóch funkcji

Z 9 uczniów wybieramy przewodniczącego i zastępcę. Na ile sposobów można obsadzić funkcje, jeżeli Ewa musi otrzymać dokładnie jedną z nich?

  1. Ewa może zostać przewodniczącą albo zastępczynią: mamy $2$ możliwości.
  2. Drugą funkcję może otrzymać dowolna z pozostałych $8$ osób.
  3. Stosujemy regułę mnożenia.
$$2\cdot8=16$$

Odpowiedź: warunek spełnia $16$ sposobów obsadzenia funkcji.

Zadanie 4

Z 8 finalistów przyznajemy złoty, srebrny i brązowy medal. Anna nie może zdobyć złotego medalu. Ile jest możliwych wyników podium?

Rozwiązanie krok po kroku
  1. Złoty medal może otrzymać jedna z $7$ osób innych niż Anna.
  2. Po przyznaniu złota na srebrny medal pozostaje $7$ kandydatów, w tym Anna.
  3. Na brązowy medal pozostaje $6$ kandydatów.
  4. $7\cdot7\cdot6=294$.
Odpowiedź: istnieją $294$ możliwe wyniki podium.
6

Warunek „co najmniej jeden” i dopełnienie

Gdy bezpośrednie liczenie wymaga wielu przypadków, wygodniej policzyć wszystkie wyniki i odjąć te, które nie zawierają ani jednego wymaganego elementu.

Schemat dopełnienia$$\text{wyniki spełniające warunek}=\text{wszystkie wyniki}-\text{wyniki niespełniające warunku}.$$
Przykład rozwiązany krok po kroku

PIN z co najmniej jednym zerem

Ile czterocyfrowych kodów PIN zawiera co najmniej jedno zero?

  1. Wszystkich kodów jest $10^4=10000$.
  2. Kod bez zera budujemy z cyfr $1,2,\ldots,9$, więc takich kodów jest $9^4=6561$.
  3. Od liczby wszystkich kodów odejmujemy liczbę kodów bez zera.
$$10^4-9^4=10000-6561=3439$$

Odpowiedź: istnieje $3439$ kodów zawierających co najmniej jedno zero.

Zadanie 5

Czteroznakowy kod tworzymy z 6 znaków. Znaki mogą się powtarzać. Ile kodów zawiera co najmniej jedno powtórzenie?

Rozwiązanie krok po kroku
  1. Wszystkich kodów z powtórzeniami jest $6^4=1296$.
  2. Kod bez żadnego powtórzenia jest wariacją bez powtórzeń: $6\cdot5\cdot4\cdot3=360$.
  3. Zdarzenia „co najmniej jedno powtórzenie” oraz „wszystkie znaki różne” są dopełnieniami.
  4. $1296-360=936$.
Odpowiedź: istnieje $936$ kodów z co najmniej jednym powtórzeniem.

Zadanie 6

Ile pięciocyfrowych kodów z cyfr od $0$ do $9$ zawiera dokładnie jedno zero? Pozostałe cyfry mogą się powtarzać.

Rozwiązanie krok po kroku
  1. Miejsce jedynego zera wybieramy na $5$ sposobów.
  2. Każdą z czterech pozostałych pozycji wypełniamy jedną z $9$ niezerowych cyfr.
  3. Niezerowe cyfry mogą się powtarzać, więc otrzymujemy $9^4$ wypełnień.
  4. $5\cdot9^4=5\cdot6561=32805$.
Odpowiedź: istnieje $32805$ takich kodów.
7

Model mieszany: różne zbiory znaków

Jeżeli kolejne części wyniku podlegają różnym zasadom, liczymy je osobno. Na przykład litery mogą nie powtarzać się, a cyfry mogą się powtarzać. Wyniki etapów łączymy regułą mnożenia.

Przykład rozwiązany krok po kroku

Identyfikator z liter i cyfr

Identyfikator składa się z dwóch różnych liter wybranych spośród 7 liter oraz trzech cyfr. Cyfry mogą się powtarzać. Ile jest identyfikatorów?

  1. Pierwszą literę wybieramy na $7$ sposobów, a drugą, inną, na $6$ sposobów.
  2. Każda z trzech pozycji cyfrowych ma $10$ możliwości.
  3. Część literowa i cyfrowa są kolejnymi etapami tworzenia jednego identyfikatora.
$$V_7^2\cdot\overline{V}_{10}^3=7\cdot6\cdot10^3=42000$$

Odpowiedź: można utworzyć $42000$ identyfikatorów.

Zadanie 7

Kod ma postać LLCC: dwie różne litery wybrane spośród 5 liter, a następnie dwie różne cyfry. Ile jest takich kodów?

Rozwiązanie krok po kroku
  1. Część literową tworzymy na $5\cdot4=20$ sposobów.
  2. Pierwszą cyfrę kodu wybieramy na $10$ sposobów. Może nią być zero, ponieważ jest to kod.
  3. Druga cyfra musi być inna, więc pozostaje $9$ możliwości.
  4. $20\cdot10\cdot9=1800$.
Odpowiedź: istnieje $1800$ kodów.
8

Wariacja, permutacja czy kombinacja?

SytuacjaKolejność?Wszystkie elementy?Model
Ustawiamy wszystkie $n$ elementówtaktakpermutacja: $n!$
Obsadzamy $k$ miejsc spośród $n$ osóbtakniewariacja bez powtórzeń: $V_n^k$
Budujemy kod długości $k$ z powtórzeniamitaknie dotyczywariacja z powtórzeniami: $n^k$
Wybieramy $k$-elementową grupęnieniekombinacja: $\binom{n}{k}$
Wariacja jako wybór i ustawienie$$V_n^k=\binom{n}{k}\cdot k!$$
Permutacja jako szczególny przypadek$$V_n^n=n!$$
Porównanie krok po kroku

Trzy osoby spośród ośmiu

  1. Trzyosobową grupę wybieramy na $\binom{8}{3}=56$ sposobów.
  2. Jeżeli przydzielamy tym osobom złoto, srebro i brąz, ustawiamy je na $3!=6$ sposobów.
  3. $\binom{8}{3}\cdot3!=56\cdot6=336=V_8^3$.

Wniosek: wariacja bez powtórzeń najpierw wybiera elementy, a następnie ustawia je w kolejności.

9

Schemat rozwiązania i typowe błędy

  1. Opisz pojedynczy wynik. Ustal, czy jest to kod, liczba, podium czy obsadzenie funkcji.
  2. Policz miejsca. Ich liczba to $k$.
  3. Policz dostępne elementy. Ich liczba to $n$.
  4. Sprawdź kolejność. Jeżeli zamiana elementów zmienia wynik, rozważ wariację.
  5. Sprawdź powtórzenia i ograniczenia. Zwróć uwagę na zero, zakazane osoby i wymagane znaki.
  6. Podziel na rozłączne przypadki. Wewnątrz przypadku mnożysz, a wyniki przypadków dodajesz.
  7. Sprawdź wynik. Każdy obiekt powinien być policzony dokładnie raz.
Typowe błędy
  • Użycie kombinacji mimo tego, że role albo pozycje są różne.
  • Zastosowanie $n^k$, chociaż elementów nie wolno powtarzać.
  • Zmniejszanie liczby możliwości na kolejnych pozycjach, mimo że powtórzenia są dozwolone.
  • Traktowanie kodu jak liczby i niepotrzebne wykluczanie zera z pierwszej pozycji.
  • Dopuszczenie zera na początku liczby wielocyfrowej.
  • Liczenie warunku „co najmniej jeden” bez użycia dopełnienia i pomijanie przypadków.
  • Dodawanie przypadków, które nie są rozłączne.
10

Zadania podsumowujące

  1. Z 12 osób wybieramy przewodniczącego, zastępcę i sekretarza. Ile jest możliwości?
  2. Ile sześciocyfrowych kodów można zbudować z cyfr $0$ i $1$, jeżeli cyfry mogą się powtarzać?
  3. Ile dodatnich liczb czterocyfrowych można utworzyć z cyfr $0,1,2,3,4,5,6$, jeżeli cyfry nie mogą się powtarzać?
  4. Pięcioznakowy kod tworzymy z 8 znaków, które mogą się powtarzać. Ile kodów zawiera co najmniej jeden wskazany znak A?

Rozwiązania krok po kroku

Zadanie 1
  1. Trzy funkcje są różne, więc kolejność wyboru osób ma znaczenie.
  2. Jedna osoba nie może pełnić dwóch funkcji, zatem nie ma powtórzeń.
  3. $V_{12}^3=12\cdot11\cdot10=1320$.
Odpowiedź: $1320$ sposobów.
Zadanie 2
  1. Kod ma $6$ pozycji.
  2. Na każdej pozycji niezależnie wybieramy $0$ albo $1$.
  3. $\overline{V}_2^6=2^6=64$.
Odpowiedź: $64$ kody.
Zadanie 3
  1. Cyfrę tysięcy wybieramy spośród $1,2,3,4,5,6$: $6$ możliwości.
  2. Na miejscu setek możemy już użyć zera, ale nie cyfry wybranej wcześniej: $6$ możliwości.
  3. Na kolejne miejsca pozostaje odpowiednio $5$ i $4$ możliwości.
  4. $6\cdot6\cdot5\cdot4=720$.
Odpowiedź: $720$ liczb.
Zadanie 4
  1. Wszystkich kodów jest $8^5=32768$.
  2. Kod bez znaku A budujemy z pozostałych $7$ znaków: $7^5=16807$.
  3. Stosujemy dopełnienie: $8^5-7^5=32768-16807=15961$.
Odpowiedź: $15961$ kodów.