Wariacje bez powtórzeń

Wariacje stosujemy wtedy, gdy z jakiegoś zbioru obiektów wybieramy określoną liczbę obiektów, a kolejność, w jakiej je wybieramy, ma znaczenie.

Wyprowadzenie wzoru

Zacznijmy od typowego zadania na wariacje: na wsi co roku odbywa się konkurs w jedzeniu knedli ze śliwkami. Do finału przeszło siedmiu umorusanych zawodników. Policz, na ile sposobów tych siedmiu uczestników może zająć trzy pierwsze miejsca.

Ważne jest, żeby zauważyć, że w tym przykładzie liczy się kolejność. Jeśli na przykład wiemy, że na trzech pierwszych miejscach znajdą się Tomek, Mateusz i Bonifacy, to ta trójka daje nam łącznie sześć różnych wyników:

• Tomek, Mateusz, Bonifacy;
• Tomek, Bonifacy, Mateusz;
• Mateusz, Tomek, Bonifacy;
• Mateusz, Bonifacy, Tomek;
• Bonifacy, Tomek, Mateusz;
• Bonifacy, Mateusz, Tomek.

To wszystko są różne wyniki, a my chcemy policzyć, ile różnych wyników da się ułożyć, gdy zawodników jest 7.

Wykorzystamy do tego regułę mnożenia. Powiemy, że wybieramy trójki postaci (x₁, x₂, x₃), gdzie x₁ to zawodnik, który zajął pierwsze miejsce itd. Których zawodników możemy wstawić za x₁? Wszystkich, czyli za x₁ możemy wstawić 7 zawodników. Których możemy wstawić za x₂? Wszystkich oprócz tego, którego już wstawiliśmy na pierwsze miejsce, więc za x₂ możemy wstawić 7 − 1 = 6 zawodników. Za x₃ możemy wstawić tych zawodników, którzy nie są na pierwszym ani drugim miejscu, mamy więc 7 − 2 = 5 możliwości. Stosujemy regułę mnożenia i otrzymujemy łączną liczbę możliwości: 7 · 6 · 5 = 210.

Zauważmy, że gdybyśmy chcieli znać liczbę wszystkich możliwości na pierwszych 4 miejscach, to za x₄ możemy wstawić 7 − 3 = 4 zawodników, więc łączna liczba możliwości wyniesie 7 · 6 · 5 · 4 = 840. Co z tego wynika?

Jeśli mamy zbiór n-elementowy (tutaj w przykładzie 7 zawodników) i wybieramy z niego 3 elementy, a kolejność ma znaczenie, to wynik jest równy n · (n − 1) · (n − 2). Na pierwszym miejscu może być każdy, na kolejnym o jednego mniej itd. Stąd możemy wyprowadzić ogólny wzór dla sytuacji, gdy wybieramy k elementów ze zbioru n-elementowego: liczba możliwości będzie równa n · (n − 1) · (n − 2) · … · (n − k + 1).

Ten wzór jeszcze przekształcimy za pomocą silni. Gdy spojrzymy, jak wygląda silnia liczby siedem: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1, i jak liczyliśmy liczbę wszystkich medalowych wyników 7 · 6 · 5, to widać pewne podobieństwo. Musimy tylko pozbyć się końcówki, czyli podzielić 7! przez 4 · 3 · 2 · 1, dzięki czemu zostanie nam tylko 7 · 6 · 5. A ile wynosi wyrażenie 4 · 3 · 2 · 1? Jest równe 4!.

Możemy więc zapisać, że jeśli mamy zbiór n-elementowy i wybieramy z niego k elementów, a kolejność ma znaczenie, to mamy łącznie

$$ V_n^k = \frac{n!}{(n-k)!} $$

możliwości. Liczbę V_n^k nazywamy liczbą k-wyrazowych wariacji bez powtórzeń zbioru n-elementowego. Gdy podstawimy do wzoru liczby z konkursu jedzenia knedli:

$$ V_7^3 = \frac{7!}{(7-3)!}=\frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{4 \cdot 3 \cdot 2 \cdot 1} = 7 \cdot 6 \cdot 5 = 210. $$

Kalkulator

Poniższy kalkulator obliczy liczbę wariacji dla podanych n i k.

Rozwiązane przykłady

1. Zostańmy przy konkursie jedzenia knedli. Jak zmieniłaby się liczba możliwych wyników medalowych, gdybyśmy wiedzieli, że na konkurs przyjechał Ludwik Sznycel, który jest mistrzem i zawsze wygrywa? Czyli ile jest różnych wyników medalowych, jeśli mamy 7 zawodników, a Ludwik na pewno wygra?

To znowu prosta wariacja: pierwsze miejsce jest pewne, a z pozostałych 6 zawodników musimy ustalić, jak mogą zająć drugie i trzecie miejsce. Wybieramy więc 2 elementy ze zbioru 6-elementowego, co prowadzi do wariacji

$$ V_6^2 = \frac{6!}{(6-2)!}=30 $$

2. Dawno temu, kiedy Ludwik Sznycel nie był jeszcze takim mistrzem, regularnie plasował się w pierwszej trójce. Ile jest różnych wyników medalowych, jeśli mamy 7 zawodników, a Ludwik na pewno zdobędzie jakiś medal?

   Ten przykład różni się od poprzedniego tym, że nie wiemy, na którym miejscu Ludwik się znalazł; mógł być dopiero drugi albo nawet trzeci, czego do dziś się wstydzi. Dlatego musimy policzyć łącznie trzy różne wariacje: przypadek, gdy Ludwik wygrał, potem gdy zdobył srebrny medal, i wreszcie gdy zdobył brązowy. Za każdym razem zostają jednak tylko dwa miejsca, które może zająć ktoś inny. Jeśli na przykład Ludwik był drugi, pozostali uczestnicy mogli zająć albo pierwsze, albo trzecie miejsce. Liczymy więc znowu 2-wyrazową wariację ze zbioru 6-elementowego, tylko musimy ją policzyć trzy razy, dla trzech różnych miejsc Ludwika. Liczba wszystkich wyników jest więc równa:

   $$ 3 \cdot V_6^2 = 3 \cdot \frac{6!}{(6-2)!} = 3 \cdot 30 = 90 $$

   Zauważ, że tę trójkę przed wariacją możemy zapisać jako V₃¹, bo w rzeczywistości wybieramy jeden element (jedno konkretne miejsce) ze zbioru 3-elementowego (trzy miejsca medalowe).

3. W szkole jest 20 nauczycieli. Niedługo matura i trzeba ustalić skład komisji: jeden przewodniczący, jeden dobry członek komisji i jeden zły członek komisji. Ile jest wszystkich możliwości?

   Najpierw musimy odpowiedzieć na pytanie, czy liczy się kolejność — tak, liczy się, trzech nauczycieli możemy znowu rozstawić na sześć różnych sposobów. Teraz jest już prosto — wybieramy 3-wyrazową wariację ze zbioru 20-elementowego:

   $$ V_{20}^3 = \frac{20!}{17!}=6840. $$

4. Ile liczb trzycyfrowych możemy ułożyć z cyfr {0, 1, 2, 3, 4, 5}, jeśli żadna cyfra nie może się powtarzać?

   Czy liczy się kolejność? Tak, 123 to inna liczba niż 321. Ile jest różnych trójek? To prosta 3-wyrazowa wariacja ze zbioru 6-elementowego:

   $$ V_6^3 = \frac{6!}{3!}=120. $$

   Musimy jednak jeszcze odjąć te wariacje, które mają na pierwszym miejscu zero, bo 012 nie jest liczbą trzycyfrową. Pytanie brzmi teraz — ile jest różnych trójek, które zaczynają się od zera? W takim przypadku cyfry zmieniają się tylko na pozostałych dwóch miejscach (trójki mają postać (0, x₂, x₃)), więc szukamy, ile różnych par możemy utworzyć z cyfr {1, 2, 3, 4, 5}. To znowu proste: V₅² = 5!/3! = 20. Istnieje więc 20 trójek, które zaczynają się od zera.

   Liczb trzycyfrowych złożonych z cyfr {0, 1, 2, 3, 4, 5} jest więc 120 − 20 = 100.

5. Ile różnych liczb trzycyfrowych możemy ułożyć z cyfr {1, 2, 3, 4, 5}, jeśli żadna cyfra nie może się powtarzać, a otrzymana liczba ma być nieparzysta?

   Kolejność ma znaczenie, bo 123 to inna liczba niż 321. Układamy liczbę trzycyfrową, która jest nieparzysta, co oznacza, że na dwóch pierwszych pozycjach może stać dowolna cyfra, ale na ostatniej musi stać jedna z cyfr {1, 3, 5}. Najpierw policzymy liczbę wszystkich trójek, jakie możemy ułożyć z pięciu cyfr: V₅³ = 5! / 2! = 60.

   Każda cyfra będzie na ostatnim miejscu występować tak samo często, więc skoro mamy 5 cyfr, to każda z nich wystąpi na ostatnim miejscu 60 / 5 = 12 razy. Mamy trzy cyfry {1, 3, 5}, które mogą pojawić się na ostatnim miejscu, więc mamy 12 różnych liczb kończących się na 1, 12 liczb kończących się na 3 i 12 liczb kończących się na 5. Stosujemy regułę dodawania i otrzymujemy łącznie 12 + 12 + 12 = 36 możliwości.

6. Oblicz x, jeśli wiesz, że V_x² = 72. Innymi słowy: ze zbioru x-elementowego wybieramy pary i wiemy, że możemy wybrać łącznie 72 różne pary. Ile elementów miał zbiór, z którego wybieraliśmy pary? Rozpiszmy to:

   $$ V_x^2 = \frac{x!}{(x-2)!} = 72 $$

   Dalej przekształcamy:

   $$\begin{eqnarray} \frac{x!}{(x-2)!} &=& 72\\ \frac{x \cdot (x-1)\cdot(x-2)!}{(x-2)!} &=& 72 \\ x \cdot (x-1) &=&72\\ x^2-x&=&72\\ x^2-x-72&=&0 \end{eqnarray}$$

   To już zwykłe równanie kwadratowe, więc rozwiążemy je za pomocą wyróżnika albo możemy zapisać równanie w postaci

   $$ (x+8)\cdot(x-9)=0 $$

   z której od razu odczytamy rozwiązania: x₁ = −8 i x₂ = 9. Ujemne rozwiązanie nas nie interesuje, bo zbiór nie może mieć ujemnej liczby elementów, więc rozwiązaniem wyjściowego równania jest x = 9 — zbiór miał dziewięć elementów.