Wariacje

Używamy wariacji, gdy wybieramy określoną liczbę obiektów ze zbioru obiektów, a kolejność, w jakiej wybieramy te obiekty, ma znaczenie.

Wyprowadzanie wzoru

Zacznijmy od typowego problemu wariacyjnego: w wiosce odbywa się coroczny konkurs jedzenia pierogów ze śliwkami. Siedmiu tłustych zawodników przechodzi do rundy finałowej. Oblicz, ile jest wszystkich możliwości, aby tych siedmiu uczestników zajęło trzy pierwsze miejsca.

Należy zauważyć, że w tym przykładzie kolejność ma znaczenie. Na przykład, jeśli wiemy, że Tonda, Matěj i Koloděj zajmą pierwsze trzy miejsca, to to trio wygeneruje w sumie sześć różnych miejsc:

• Tonda, Matěj, Koloděj;
• Tonda, Kolodej, Matěj;
• Matěj, Tonda, Koloděj;
• Matěj, Koloděj, Tonda;
• Koloděj, Tonda, Matěj;
• Koloděj, Matěj, Tonda.

Są to różne miejsca docelowe i chcemy obliczyć, ile różnych miejsc docelowych możemy połączyć, gdy jest 7 konkurentów.

W tym celu wykorzystujemy regułę iloczynu kombinatorycznego. Załóżmy, że wybieramy trójki w postaci [x₁, x₂, x₃], gdzie x₁ to zawodnik, który zajął pierwsze miejsce itd. Których zawodników możemy umieścić po x₁? Wszystkich, więc możemy umieścić 7 zawodników po x₁. Których zawodników możemy umieścić po x₂? Wszystkich, z wyjątkiem tego, którego umieściliśmy już na pierwszym miejscu, więc możemy umieścić 7 − 1 = 6 po x₂. Następnie możemy umieścić zawodników, którzy nie są na pierwszym lub drugim miejscu za x₃, więc mamy opcje 7 − 2 = 5. Stosujemy regułę iloczynu kombinatorycznego i otrzymujemy całkowitą liczbę możliwości: 7 · 6 · 5 = 210.

Możemy zauważyć, że jeśli chcemy poznać liczbę wszystkich możliwości na pierwszych 4 miejscach, możemy umieścić 7 − 3 = 4 zawodników za x₄, więc całkowita liczba możliwości wynosi 7 · 6 · 5 · 4 = 840. Co możemy z tego wywnioskować?

Jeśli mamy zbiór n elementów (7 zjadaczy w tym przykładzie) i wybierzemy 3 elementów, w zależności od kolejności, wynik jest równy n · (n − 1) · (n − 2). Wszystkie z nich mogą być na pierwszym miejscu, jeden mniej na kolejnym miejscu i tak dalej. Na tej podstawie możemy wyprowadzić ogólny wzór dla sytuacji, gdy wybieramy elementy k ze zbioru elementów n: liczba możliwości będzie równa n · (n − 1) · (n − 2) · … · (n − k + 1).

Modyfikujemy ten wzór jeszcze bardziej, używając czynnika. Kiedy spojrzymy na to, jak wygląda czynnik siedem: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 i jak policzyliśmy liczbę wszystkich miejsc medalowych 7 · 6 · 5, widzimy pewne podobieństwo. Musimy tylko pozbyć się końcówki, tj. musimy podzielić 7! przez 4 · 3 · 2 · 1, co pozostawia nam tylko 7 · 6 · 5. A co jest równe wyrażeniu 4 · 3 · 2 · 1? Jest ono równe 4!.

Możemy więc napisać, że jeśli mamy zbiór n elementów i wybierzemy w sumie k elementów, w zależności od kolejności, mamy w sumie

$$ V(k, n) = \frac{n!}{(n-k)!} $$

możliwości. Jeśli podłączymy liczby z wyścigu śliwek do tego wzoru:

$$ V(3, 7) = \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. $$

Komputer

Poniższy kalkulator obliczy liczbę wariacji dla danego n i k, włączając w to procedurę.

Rozwiązane przykłady

1. Pozostańmy przy wyścigu w jedzeniu pierogów. Jak zmieniłaby się liczba możliwych miejsc medalowych, gdybyśmy wiedzieli, że w wyścigu weźmie udział Ludva Schnitzell, która jest macho i zawsze wygrywa? Tzn. ile jest różnych miejsc medalowych, jeśli mamy 7 zawodników, a Ludva na pewno wygra?

Ponownie, jest to prosta wariacja, pierwsze miejsce jest pewne, a z pozostałych 6 zawodników pozostaje nam określić, w jaki sposób mogą wypełnić drugie i trzecie miejsce. Wybieramy więc 2 elementy z 6-elementowego zestawu, co prowadzi do wariacji

$$ V(2, 6) = \frac{6!}{(6-2)!}=30 $$

2. Dawno, dawno temu, kiedy Ludva Schnitzell nie był tak wielkim zawodnikiem, regularnie plasował się w pierwszej trójce. Ile jest różnych miejsc medalowych, jeśli mamy 7 zawodników, a Ludva na pewno zdobędzie medal?

   Ten przykład różni się od poprzedniego tym, że nie wiemy, na którym miejscu uplasował się Ludva; mógł zająć nawet drugie lub nawet trzecie miejsce, czego wciąż się wstydzi. Dlatego musimy obliczyć w sumie trzy różne warianty: gdyby Ludva wygrał, następnie gdyby Ludva zdobył srebrny medal i wreszcie brązowy medal. Oczywiście za każdym razem pozostają tylko dwa miejsca, na których ktoś inny może się uplasować. Na przykład, gdyby Ludva była druga, pozostali uczestnicy mogliby zająć pierwsze lub trzecie miejsce. W związku z tym ponownie liczymy dwuosobową wariację sześciu, tylko że musimy ją policzyć trzy razy, dla trzech różnych miejsc Ludvy. Liczba wszystkich miejsc jest zatem równa:

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

   Zauważ, że możemy zapisać trzy przed wariacją jako V(1, 3), ponieważ w rzeczywistości wybieramy jeden element (jedno konkretne miejsce) z trzyelementowego zbioru (trzy pozycje medalowe).

3. W szkole jest łącznie 20 nauczycieli. Wkrótce odbędzie się matura i musimy utworzyć komisję w następującym składzie: jeden przewodniczący, jeden dobry przewodniczący i jeden zły przewodniczący. Ile jest w sumie opcji?

   Pierwszym pytaniem, na które musimy odpowiedzieć, jest to, czy kolejność ma znaczenie - tak, możemy ponownie rzucić trzech nauczycieli na sześć różnych sposobów. Teraz sprawa jest prosta - wybieramy 3-osobową wariację z 20 elementów:

   $$ V(3, 20) = \frac{20!}{17!}=6840. $$

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

   Czy kolejność ma znaczenie? Tak, to zależy, 123 jest inną liczbą niż 321. Ile jest różnych trójek? To prosta 3-cyfrowa wariacja liczby 6:

   $$ V(3, 6) = \frac{6!}{3!}=120. $$

   Ale nadal musimy odjąć wariacje, które mają zero na pierwszym miejscu, ponieważ 012 nie jest liczbą trzycyfrową. Pytanie brzmi więc: ile jest różnych trójek zaczynających się od zera? W tym przypadku tylko cyfry na pozostałych dwóch miejscach są naprzemienne (trójki mają postać [0, x₂, x₃]), więc chcemy zobaczyć, ile różnych par możemy utworzyć przy użyciu liczb {1, 2, 3, 4, 5}. Ponownie, jest to łatwe: V(2, 5) = 5!/3! = 20. Istnieje zatem 20 trójek zaczynających się od zera.

   Zatem całkowita liczba liczb trzycyfrowych, które składają się z cyfr {0, 1, 2, 3, 4, 5}, wynosi 120 − 20 = 100.

5. Ile różnych liczb trzycyfrowych możemy zbudować z cyfr {1, 2, 3, 4, 5}, jeśli żadna cyfra nie może się powtórzyć, a wynikowa liczba ma być nieparzysta?

   Kolejność ma znaczenie, ponieważ 123 jest inną liczbą niż 321. Tworzymy liczbę trzycyfrową, która jest nieparzysta, co oznacza, że pierwsze dwie pozycje mogą mieć dowolną cyfrę, ale ostatnia pozycja musi mieć jedną z cyfr {1, 3, 5}. Najpierw policzymy liczbę wszystkich trójek, które możemy ułożyć z pięciu cyfr: V(3, 5) = 5! / 2! = 60.

   Każda cyfra pojawi się na ostatniej pozycji równie często, więc jeśli mamy 5 cyfr, każda cyfra pojawi się na ostatniej pozycji 60 / 5 = 12razy. Mamy trzy cyfry {1, 3, 5}, które mogą pojawić się na ostatnim miejscu, więc mamy 12 różnych liczb, które kończą się na 1, 12 liczb, które kończą się na 3 do 12 liczb, które kończą się na 5. Stosujemy regułę sumy kombinatorycznej i otrzymujemy łącznie 12 + 12 + 12 = 36 możliwości.

6. Oblicz x, jeśli wiesz, że V(2, x) = 72. Innymi słowy: wybieramy pary ze zbioru o rozmiarze x i wiemy, że jesteśmy w stanie wybrać w sumie 72 różnych par. Jak duży był zbiór, z którego wybraliśmy pary? Rozbijmy to na czynniki pierwsze:

   $$ V(2, x) = \frac{x!}{(x-2)!} = 72 $$

   Następnie modyfikujemy:

   $$\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}$$

   Jest to już klasyczne równanie kwadratowe, więc rozwiązujemy je za pomocą wyróżnika lub możemy przepisać równanie w postaci

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

   z którego możemy już odczytać rozwiązanie: x₁ = −8 i x₂ = 9. Nie obchodzi nas rozwiązanie ujemne, ponieważ zbiór nie może mieć rozmiaru ujemnego, więc rozwiązaniem oryginalnego równania jest x = 9, zbiór miał dziewięć elementów.

Źródła i dalsze lektury

• Kombinatoryka na cuni.cz
• Bělohlávek, Vychodil: Matematyka dyskretna [PDF]