K-permutaatio

K-permutaatiota käytämme, kun valitsemme jostakin objektien joukosta tietyn määrän objekteja ja valintajärjestyksellä on väliä.

Kaavan johto

Aloitetaan tyypillisellä k-permutaatiotehtävällä: kylässä järjestetään joka vuosi mustikkapiirakan syöntikilpailu. Loppukilpailuun on päässyt yhteensä seitsemän tahraista kilpailijaa. Laske, kuinka monella tavalla nämä seitsemän osallistujaa voivat sijoittua kolmelle ensimmäiselle sijalle.

On tärkeää huomata, että tässä esimerkissä järjestyksellä on väliä. Jos esimerkiksi tiedämme, että kolmella ensimmäisellä sijalla ovat Eino, Leevi ja Onni, tämä kolmikko tuottaa yhteensä kuusi erilaista sijoitusta:

• Eino, Leevi, Onni;
• Eino, Onni, Leevi;
• Leevi, Eino, Onni;
• Leevi, Onni, Eino;
• Onni, Eino, Leevi;
• Onni, Leevi, Eino.

Kaikki nämä ovat eri sijoituksia, ja haluamme laskea, kuinka monta erilaista sijoitusta voimme muodostaa, kun kilpailijoita on 7.

Käytämme siihen kombinatoriikan tuloperiaatetta. Sanomme, että valitsemme kolmikoita muotoa (x₁, x₂, x₃), missä x₁ on ensimmäiseksi sijoittunut kilpailija jne. Ketkä kilpailijat voimme sijoittaa kohtaan x₁? Kaikki, eli kohtaan x₁ voimme sijoittaa 7 kilpailijaa. Ketkä voimme sijoittaa kohtaan x₂? Kaikki paitsi se, jonka sijoitimme jo ensimmäiseksi, joten kohtaan x₂ voimme sijoittaa 7 − 1 = 6 kilpailijaa. Kohtaan x₃ voimme sijoittaa ne kilpailijat, jotka eivät ole ensimmäisellä eivätkä toisella sijalla, joten vaihtoehtoja on 7 − 2 = 5. Soveltamme tuloperiaatetta ja saamme vaihtoehtojen kokonaismäärän: 7 · 6 · 5 = 210.

Huomaamme, että jos haluaisimme tietää vaihtoehtojen määrän neljälle ensimmäiselle sijalle, kohtaan x₄ voisimme sijoittaa 7 − 3 = 4 kilpailijaa, joten vaihtoehtojen kokonaismäärä olisi 7 · 6 · 5 · 4 = 840. Mitä tästä voimme päätellä?

Jos meillä on joukko, jossa on n alkiota (tässä esimerkissä 7 syöjää), ja valitsemme 3 alkiota niin, että järjestyksellä on väliä, tulos on n · (n − 1) · (n − 2). Ensimmäiselle sijalle voivat sijoittua kaikki, seuraavalle yksi vähemmän jne. Tästä voimme johtaa yleisen kaavan tilanteeseen, jossa valitsemme k alkiota joukosta, jossa on n alkiota: vaihtoehtojen määrä on n · (n − 1) · (n − 2) · … · (n − k + 1).

Muokkaamme tätä kaavaa vielä kertoman avulla. Kun katsomme, miltä seitsemän kertoma näyttää: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1, ja miten laskimme kaikkien palkintosijoitusten määrän 7 · 6 · 5, huomaamme tietyn yhtäläisyyden. Tarvitsee vain päästä eroon lopusta eli jakaa 7! tulolla 4 · 3 · 2 · 1, jolloin jäljelle jää vain 7 · 6 · 5. Ja mitä tulo 4 · 3 · 2 · 1 on? Se on 4!.

Voimme siis kirjoittaa, että jos joukossa on n alkiota ja valitsemme k alkiota niin, että järjestyksellä on väliä, vaihtoehtoja on yhteensä

$$\frac{n!}{(n-k)!}$$

Tämä on n alkion k-permutaatioiden lukumäärä. Kun sijoitamme kaavaan luvut mustikkapiirakkakilpailusta (n = 7, k = 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.$$

Laskin

Seuraava laskin laskee k-permutaatioiden lukumäärän annetuille n:lle ja k:lle.

Ratkaistuja esimerkkejä

1. Pysytään syöntikilpailussa. Miten palkintosijoitusten määrä muuttuisi, jos tietäisimme, että kilpailuun on tullut Elias, joka on mestari ja voittaa aina? Eli kuinka monta erilaista palkintosijoitusta on olemassa, kun kilpailijoita on 7 ja Elias voittaa varmasti?

Tämäkin on yksinkertainen k-permutaatio: ensimmäinen sija on varma, ja jäljellä olevista 6 kilpailijasta on vielä päätettävä, miten he voivat täyttää toisen ja kolmannen sijan. Valitsemme siis 2 alkiota 6 alkion joukosta, mikä johtaa lukuun

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

2. Kauan sitten, kun Elias ei vielä ollut mestari, hän sijoittui säännöllisesti kolmen parhaan joukkoon. Kuinka monta erilaista palkintosijoitusta on olemassa, kun kilpailijoita on 7 ja Elias saa varmasti jonkin mitalin?

   Tämä esimerkki eroaa edellisestä siinä, ettemme tiedä, millä sijalla Elias sijoittui. Hän on voinut sijoittua vasta toiseksi tai jopa kolmanneksi, mitä hän häpeää vieläkin. Siksi meidän on laskettava yhteensä kolme eri k-permutaatiota: tapaus, jossa Elias voitti, sitten tapaus, jossa Elias sai hopeaa, ja lopuksi tapaus, jossa hän sai pronssia. Joka kerralla jää kuitenkin vain kaksi sijaa, joille joku muu voi sijoittua. Jos Elias oli esimerkiksi toinen, muut osallistujat saattoivat sijoittua joko ensimmäiseksi tai kolmanneksi. Lasketaan siis jälleen kahden alkion k-permutaatio kuudesta, mutta se on laskettava kolme kertaa, Eliaksen kolmelle eri sijoitukselle. Kaikkien sijoitusten määrä on siis:

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

   Huomaa, että tuon k-permutaation edessä olevan kolmosen voi kirjoittaa muodossa $\frac{3!}{(3-1)!}$, koska todellisuudessa valitsemme yhden alkion (yhden tietyn sijoituksen) kolmen alkion joukosta (kolme mitalisijaa).

3. Koulussa on yhteensä 20 opettajaa. Pian on ylioppilaskirjoitukset, ja on koottava lautakunta, jossa on yksi puheenjohtaja, yksi kiltti jäsen ja yksi ankara jäsen. Kuinka monta mahdollisuutta on yhteensä?

   Ensin on vastattava kysymykseen, onko järjestyksellä väliä. On, kolme opettajaa voidaan taas järjestää kuudella eri tavalla. Nyt se on helppoa: valitsemme 3 alkion k-permutaation 20 alkiosta:

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

4. Kuinka monta kolminumeroista lukua voimme koota numeroista {0, 1, 2, 3, 4, 5}, kun mikään numero ei saa toistua?

   Onko järjestyksellä väliä? On, 123 on eri luku kuin 321. Kuinka monta erilaista kolmikkoa on olemassa? Se on yksinkertainen 3 alkion k-permutaatio 6 alkiosta:

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

   Mutta meidän on vielä vähennettävä ne k-permutaatiot, joiden ensimmäisenä numerona on nolla, koska 012 ei ole kolminumeroinen luku. Kysymys kuuluu nyt: kuinka monta erilaista kolmikkoa alkaa nollalla? Tällöin numerot vaihtelevat vain jäljellä olevilla kahdella paikalla (kolmikot ovat muotoa (0, x₂, x₃)), joten etsimme, kuinka monta erilaista paria voimme muodostaa numeroista {1, 2, 3, 4, 5}. Se on taas yksinkertaista: $\frac{5!}{(5-2)!}=5!/3!=20$. Nollalla alkavia kolmikkoja on siis 20.

   Numeroista {0, 1, 2, 3, 4, 5} koostuvien kolminumeroisten lukujen kokonaismäärä on siis 120 − 20 = 100.

5. Kuinka monta erilaista kolminumeroista lukua voimme muodostaa numeroista {1, 2, 3, 4, 5}, kun mikään numero ei saa toistua ja tuloksen on oltava pariton?

   Järjestyksellä on väliä, koska 123 on eri luku kuin 321. Muodostamme kolminumeroisen luvun, jonka on oltava pariton, mikä tarkoittaa, että kahdella ensimmäisellä paikalla voi olla mikä tahansa numero, mutta viimeisellä on oltava jokin numeroista {1, 3, 5}. Ensin lasketaan kaikkien kolmikoiden määrä, jotka voimme koota viidestä numerosta: $\frac{5!}{(5-3)!}=5!/2!=60$.

   Jokainen numero esiintyy viimeisellä paikalla yhtä usein, joten kun numeroita on 5, jokainen numero on viimeisenä 60 / 5 = 12 kertaa. Meillä on kolme numeroa {1, 3, 5}, jotka voivat olla viimeisenä, joten meillä on 12 eri lukua, jotka päättyvät ykköseen, 12 lukua, jotka päättyvät kolmoseen, ja 12 lukua, jotka päättyvät viitoseen. Käytämme summaperiaatetta ja saamme yhteensä 12 + 12 + 12 = 36 vaihtoehtoa.

6. Laske x, kun tiedät, että $\frac{x!}{(x-2)!}=72$. Toisin sanoen: valitsemme pareja joukosta, jossa on x alkiota, ja tiedämme, että voimme valita yhteensä 72 eri paria. Kuinka suuri oli joukko, josta pareja valittiin? Kirjoitetaan auki:

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

   Muokataan edelleen:

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

   Tämä on jo tavallinen toisen asteen yhtälö, joten ratkaisemme sen diskriminantin avulla tai voimme kirjoittaa yhtälön muotoon

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

   josta ratkaisut voi jo lukea: x₁ = −8 ja x₂ = 9. Negatiivinen ratkaisu ei kiinnosta meitä, koska joukon koko ei voi olla negatiivinen, joten alkuperäisen yhtälön ratkaisu on x = 9, joukossa oli yhdeksän alkiota.