Variációk

Variációt akkor használunk, ha egy objektumhalmazból meghatározott számú objektumot választunk ki, és számít, milyen sorrendben választjuk ki őket.

A képlet levezetése

Kezdjük egy tipikus variációs feladattal: egy faluban minden évben szilvásgombóc-evő versenyt rendeznek. A döntőbe összesen hét zsíros szájú versenyző jutott. Számold ki, hányféleképpen foglalhatja el ez a hét versenyző az első három helyet.

Fontos észrevenni, hogy ebben a példában a sorrend számít. Ha például tudjuk, hogy az első három helyen Tóni, Máté és Kálmán végez, akkor ez a hármas hat különböző helyezést ad:

• Tóni, Máté, Kálmán;
• Tóni, Kálmán, Máté;
• Máté, Tóni, Kálmán;
• Máté, Kálmán, Tóni;
• Kálmán, Tóni, Máté;
• Kálmán, Máté, Tóni.

Ezek mind különböző helyezések, és azt akarjuk kiszámolni, hány különböző helyezést tudunk összeállítani, ha 7 versenyző van.

Ehhez a kombinatorikai szorzatszabályt használjuk. Azt mondjuk, hogy az (x₁; x₂; x₃) alakú hármasokat választjuk, ahol x₁ az első helyen végzett versenyző stb. Kiket helyettesíthetünk x₁ helyére? Mindenkit, vagyis x₁ helyére 7 versenyzőt írhatunk. Kiket írhatunk x₂ helyére? Mindenkit, kivéve azt, akit már az első helyre tettünk, tehát x₂ helyére 7 − 1 = 6 versenyzőt írhatunk. x₃ helyére azokat írhatjuk, akik nem az első vagy a második helyen vannak, így 7 − 2 = 5 lehetőségünk van. Alkalmazzuk a kombinatorikai szorzatszabályt, és megkapjuk a lehetőségek teljes számát: 7 · 6 · 5 = 210.

Megfigyelhetjük, hogy ha az első 4 hely lehetőségeinek számát akarjuk tudni, akkor x₄ helyére 7 − 3 = 4 versenyzőt írhatunk, így a lehetőségek száma 7 · 6 · 5 · 4 = 840 lesz. Mit következtethetünk ebből?

Ha van egy n elemű halmazunk (itt a példában 7 evő), és 3 elemet választunk ki úgy, hogy számít a sorrend, akkor az eredmény n · (n − 1) · (n − 2). Az első helyre mindenki kerülhet, a következőre eggyel kevesebben stb. Ebből levezethetjük az általános képletet arra az esetre, amikor egy n elemű halmazból k elemet választunk: a lehetőségek száma n · (n − 1) · (n − 2) · … · (n − k + 1).

Ezt a képletet még tovább alakítjuk a faktoriális segítségével. Ha megnézzük, hogyan néz ki a hét faktoriálisa: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1, és hogyan számoltuk ki az összes érmes helyezés számát, 7 · 6 · 5, bizonyos hasonlóságot látunk. Csak a végétől kell megszabadulnunk, vagyis a 7!-t el kell osztanunk a 4 · 3 · 2 · 1 szorzattal, így csak 7 · 6 · 5 marad. És mivel egyenlő a 4 · 3 · 2 · 1 kifejezés? Egyenlő 4!-sal.

Felírhatjuk tehát, hogy ha van egy n elemű halmazunk, és összesen k elemet választunk ki úgy, hogy számít a sorrend, akkor összesen

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

lehetőségünk van. Ha behelyettesítjük a képletbe a szilvásgombóc-verseny számait:

$$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.$$

Számológép

A következő számológép kiszámolja a variációk számát adott n és k esetén.

Megoldott példák

1. Maradjunk a gombócevő versenynél. Hogyan változna az érmes helyezések száma, ha tudnánk, hogy a versenyre megérkezett Lajcsi Schnitzel, aki igazi nagymenő, és mindig nyer? Vagyis hány különböző érmes helyezés van, ha 7 versenyző van, és Lajcsi biztosan nyer?

   Ez megint egyszerű variáció: az első hely biztos, a maradék 6 versenyzőről pedig azt kell meghatároznunk, hányféleképpen tölthetik be a második és a harmadik helyet. Tehát 2 elemet választunk egy 6 elemű halmazból, ami a következő variációhoz vezet:

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

2. Réges-régen, amikor Lajcsi Schnitzel még nem volt ilyen nagymenő, rendszeresen az első három között végzett. Hány különböző érmes helyezés van, ha 7 versenyző van, és Lajcsi biztosan kap valamilyen érmet?

   Ez a példa abban különbözik az előzőtől, hogy nem tudjuk, hányadik helyen végzett Lajcsi. Lehetett második, sőt akár harmadik is, amit a mai napig szégyell. Ezért összesen három különböző variációt kell kiszámolnunk: arra az esetre, amikor Lajcsi nyert, aztán amikor ezüstérmes lett, és végül amikor bronzérmes. Mindig csak két hely marad, ahová valaki más kerülhet. Ha például Lajcsi második volt, a többiek az első vagy a harmadik helyen végezhettek. Megint hat elem kéttagú variációit számoljuk, csak háromszor kell kiszámolnunk, Lajcsi három különböző helyezésére. Az összes helyezés száma tehát:

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

   Figyeld meg, hogy a variáció előtti hármast felírhatjuk $V_3^1$-ként is, mert valójában egy elemet (egy konkrét helyezést) választunk egy háromelemű halmazból (három érmes hely).

3. Egy iskolában összesen 20 tanár van. Hamarosan érettségi lesz, és össze kell állítani a bizottságot a következő összetételben: egy elnök, egy jóindulatú tag és egy szigorú tag. Hány lehetőség van összesen?

   Először azt kell megválaszolnunk, hogy számít-e a sorrend. Igen, számít, a három tanárt megint hatféleképpen lehet felcserélni. Innen már egyszerű, 20 elem 3 tagú variációit számoljuk:

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

4. Hány háromjegyű számot állíthatunk össze a {0, 1, 2, 3, 4, 5} számjegyekből, ha egyetlen számjegy sem ismétlődhet?

   Számít a sorrend? Igen, a 123 más szám, mint a 321. Hány különböző hármas létezik? Ez egyszerűen 6 elem 3 tagú variációinak száma:

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

   De még le kell vonnunk azokat a variációkat, amelyek nullával kezdődnek, mert a 012 nem háromjegyű szám. A kérdés tehát most az: hány különböző hármas kezdődik nullával? Ilyenkor csak a másik két helyen váltakoznak a számjegyek (a hármasok alakja (0; x₂; x₃)), tehát azt keressük, hány különböző kettest alkothatunk az {1, 2, 3, 4, 5} számokból. Ez megint egyszerű: $V_5^2=5!/3!=20$. Tehát 20 olyan hármas van, amely nullával kezdődik.

   A {0, 1, 2, 3, 4, 5} számjegyekből összeállított háromjegyű számok száma így 120 − 20 = 100.

5. Hány különböző háromjegyű számot tudunk összeállítani az {1, 2, 3, 4, 5} számjegyekből, ha egyetlen számjegy sem ismétlődhet, és a kapott szám páratlan legyen?

   A sorrend számít, mert a 123 más szám, mint a 321. Páratlan háromjegyű számot állítunk össze, ami azt jelenti, hogy az első két helyen bármelyik számjegy állhat, az utolsón viszont az {1, 3, 5} számjegyek egyikének kell állnia. Először kiszámoljuk az összes hármas számát, amelyet az öt számjegyből össze tudunk állítani: $V_5^3=5!/2!=60$.

   Minden számjegy ugyanolyan gyakran szerepel az utolsó helyen, tehát ha 5 számjegyünk van, akkor mindegyik 60 / 5 = 12-szer szerepel az utolsó helyen. Három számjegy, az {1, 3, 5} állhat az utolsó helyen, így 12 különböző számunk végződik 1-esre, 12 szám 3-asra és 12 szám 5-ösre. Alkalmazzuk az összegszabályt, és összesen 12 + 12 + 12 = 36 lehetőséget kapunk.

6. Számítsd ki x-et, ha tudod, hogy $V_x^2=72$. Másképp mondva: egy x elemű halmazból ketteseket választunk, és tudjuk, hogy összesen 72 különböző kettest tudunk kiválasztani. Mekkora volt a halmaz, amelyből a ketteseket választottuk? Írjuk fel:

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

   Ezután alakítunk:

   $$\begin{array}{rcl}\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{array}$$

   Ez már egy klasszikus másodfokú egyenlet, megoldhatjuk a diszkrimináns segítségével, vagy átírhatjuk az egyenletet

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

   alakba, amelyből már leolvashatjuk a megoldást: x₁ = −8 és x₂ = 9. A negatív megoldás nem érdekel minket, mert egy halmaznak nem lehet negatív az elemszáma, ezért az eredeti egyenlet megoldása x = 9, a halmaznak kilenc eleme volt.