Permutaatio vs. yhdistelmä: Mitä eroa on permutaatiokaavalla ja yhdistelmäkaavalla?

Permutaatio vs. yhdistelmä: Mitä eroa on permutaatiokaavalla ja yhdistelmäkaavalla?

Tässä on lyhyt versio.

Voidaan ottaa esimerkkinä kirkon kellojen soitto.

Permutaatio on kellojen järjestys. Mietit parasta järjestystä, jossa niitä soitetaan.

Yhdistelmä on kellojen valinta. Valitset soitettavat kellot. Jos sinulla on liikaa kelloja, valitset ne ensin ja mietit sitten niiden järjestystä.

Tästä syntyy tuttu identiteetti: (n P r) = (n C r) * r!

Tapa tilata r kappaletta n:sta on valita ensin r kappaletta n:sta ja sitten tilata r kappaletta (r! )

Ja tämä tarkoittaa (n P r) = n! / (n-r)! ja (n C r) = n! / ( (n-r)! * r! )

Mutta haluatko tietää, miten muistat tämän ikuisiksi ajoiksi?

Olen suuri ensimmäisten periaatteiden ajattelun ystävä. Ymmärtääksesi ongelman, mene sen ytimeen ja päättele sieltä ylöspäin.

Ei näin tehdä, se on yleensä hämmennyksen lähde: jos en ymmärrä, miten asiat toimivat, en tiedä mihin ripustaa käsitteitä. Psyykkinen kehykseni ei ole täydellinen, joten päätän vain muistaa sen.

Kuten voitte kuvitella, tämä ei ole ihanteellista. Joten aika ajoin hemmottelen itseäni harjoituksella, jossa johdan asioita lähteestä ja rakennan intuitiota siitä, miten asiat toimivat.

Tällä kertaa rakennamme intuitiota permutaatioista ja yhdistelmistä.

Tiedätkö esimerkiksi, miksi yhdistelmän kaava on (n C r)? Mistä tämä on peräisin? Ja miksi tässä käytetään faktoriaaleja?

Aloitetaan lähteestä. Faktoriaalit, permutaatiot ja kombinaatiot syntyivät yhdessä leikkivistä matemaatikoista, aivan kuten Steve Jobs ja Steve Wozniak perustivat Applen leikkimällä yhdessä autotallissaan.

Aivan kuten Applesta tuli täysimittainen kannattava yritys, yksinkertaisesta faktoriaalista, !, tuli kokonaisen matematiikan alan atomi: kombinatoriikka.

Unohda kaikki, aletaan ajatella alhaalta ylöspäin.

Ensimmäinen tunnettu mielenkiintoinen käyttötapaus tuli kirkkoihin 1600-luvulla.

Oletko miettinyt, miten kelloja soitetaan kirkoissa? Siellä on kone, joka ”soittaa” niitä järjestyksessä. Siirryttiin koneisiin, koska kellot ovat liian suuria. Lisäksi kelloja on valtavasti.

Miten ihmiset keksivät parhaan järjestyksen, jossa niitä soitetaan? Entä jos he halusivat vaihtaa asioita? Miten he löysivät parhaan äänen? Jokaisessa kellotornissa oli jopa 16 kelloa!

Ei voinut muuttaa sitä, kuinka nopeasti kelloa pystyi soittamaan – koneet soittivat vain yhtä kelloa joka sekunti. Ainoa, mitä voit tehdä, oli muuttaa kellojen järjestystä. Tässä haasteessa oli siis kyse parhaan järjestyksen selvittämisestä.

Voisimmeko matkan varrella selvittää myös kaikki mahdolliset järjestykset? Haluamme tietää kaikki mahdolliset järjestykset, jotta voimme selvittää, kannattaako niitä kaikkia kokeilla.

Kellonsoittaja Fabian Stedman tarttui tähän haasteeseen.

Hän aloitti kahdella kellolla. Missä eri järjestyksissä hän voisi soittaa näitä kelloja?

1 ja 2.
tai
2 ja 1.

Tässä oli järkeä. Muuta tapaa ei ollut.

Miten olisi kolmen kellon kanssa?

1, 2 ja 3.
1, 3 ja 2.

Alkaen toisesta kellosta,

2, 1 ja 3.
2, 3 ja 1.

Alkaen kolmannesta kellosta,

3, 1 ja 2.
3, 2 ja 1.

yhteensä 6.

Hän tajusi sitten, että tämä oli hyvin samankaltaista kuin kaksi kelloa!

Jos hän korjasi ensimmäisen kellon, niin jäljellä olevien kahden kellon järjestysmuotojen määrä oli aina kaksi.

Miten monella tavalla hän voisi korjata ensimmäisen kellon? Mikä tahansa kolmesta kellosta voisi olla se yksi!

Okei, hän jatkoi. Sitten hän pääsi viiteen kelloon.

Tällöin hän tajusi, että käsin tekeminen on hankalaa. Sinulla on vain niin paljon aikaa päivässä, sinun täytyy soittaa kelloja, et voi jäädä vetämään kaikkia mahdollisia kelloja. Oliko olemassa keino selvittää tämä nopeasti?

Hän palasi oivallukseensa.

Jos hänellä oli viisi kelloa ja hän korjasi ensimmäisen kellon, hänen piti vain keksiä, miten tilata neljä kelloa.

Neljään kelloon? No, jos hänellä oli 4 kelloa ja hän korjasi ensimmäisen kellon, hänen piti vain keksiä, miten tilata 3 kelloa.

Ja hän tiesi, miten se tehdään!

Siten 5 kellon tilaaminen = 5 * 4 kellon tilaaminen.

4 kellon tilaaminen = 4 * 3 kellon tilaaminen

3 kellon tilaaminen = 3 * 2 kellon tilaaminen.

… Huomaathan kaavan?

Hauska fakta: Tämä on avain ohjelmointitekniikkaan nimeltä rekursio.

Hänkin huomasi. Tosin häneltä kesti paljon kauemmin, koska kukaan hänen lähellään ei ollut jo keksinyt tätä.

Siten hän keksi, että 5 kellon järjestys = 5 * 4 * 3 * 2 * 1.

Tämä järjestyskaava tuli vuonna 1808 tunnetuksi nimellä faktorikaava.

Me ajattelemme faktorikaavan merkintätapa peruskirjoitusasua, mutta ajatus oli olemassa jo kauan ennen kuin sillä oli nimi. Vasta kun ranskalainen matemaatikko Christian Kramp huomasi, että sitä käytettiin muutamissa paikoissa, hän nimesi sen faktoriaaliksi.

Tätä kellojen järjestystä kutsutaan permutaatioksi.

Permutaatio on esineiden järjestys.

Kun opettelee jotakin, mielestäni auttaa tarkastelemaan asioita jokaisesta eri näkökulmasta, jotta ymmärrys lujittuu.

Mitä jos yrittäisimme johtaa yllä olevan kaavan suoraan, yrittämättä supistaa ongelmaa pienempään määrään kelloja?
Meillä on 5 tilaa, eikö niin?

Millä monella tavalla voimme valita ensimmäisen kellon? 5, koska meillä on niin monta kelloa.

Kakkoskello? No, käytimme yhden kellon, kun laitoimme sen ensimmäiseen paikkaan, joten meillä on neljä kelloa jäljellä.

Kolmas kello? No, valitsimme kaksi ensimmäistä, joten jäljellä on enää 3 kelloa.

Neljäs kello? Vain 2 kelloa jäljellä, joten 2 vaihtoehtoa.
Viides kello? Vain 1 jäljellä, joten 1 vaihtoehto.

Ja siinäpä se, tilausten kokonaismäärä on 5 * 4 * 3 * 2 * 1

Siten meillä on ensimmäinen yleinen kaavamme.

Tapojen määrä, joilla N kohdetta voidaan tilata, on N!

Nyt olemme toisen ongelman edessä. Kuningas määräsi valmistamaan uudet kellot jokaiseen kirkkoon. Jotkut ovat kivoja, jotkut ovat ihan ok, jotkut saavat sinut kuuroutumaan. Mutta jokainen on ainutlaatuinen. Jokainen antaa oman äänensä. Kuuro kello kauniiden kellojen ympäröimänä voi kuulostaa majesteettiselta.

Mutta kellotornissamme on vielä viisi kelloa, joten meidän on keksittävä paras tilaus kahdeksasta kellosta, jotka taitavat kellontekijät tekivät.

Yllä olevaa logiikkaa käyttäen voimme edetä.

Ensimmäistä kelloa varten voimme valita minkä tahansa kahdeksasta kellosta.

Kakkoskelloa varten voimme valita minkä tahansa jäljelle jäävistä seitsemästä kellosta… ja niin edelleen.

Loppujen lopuksi saamme 8 * 7 * 6 * 5 * 4 mahdollisia järjestyksiä 8 kellolle 5 tilassa.

Jos sinulle on tuttu kaavaversio (n P r), joka on n! / (n-r)!, älä huoli, johdamme senkin pian!

Yksi huono tapa johtaa se on kertoa sekä osoittaja että nimittäjä kolmella! yllä olevassa esimerkissämme –

saamme 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3!.

Mutta tämä ei auta meitä ymmärtämään, miksi tämä kaava toimii. Ennen kuin pääsemme sinne, tarkastellaan asioiden valitsemista eli yhdistelmää.

Yhdistelmä

Nyt kun tiedämme, miten asiat järjestetään, voimme selvittää, miten asiat valitaan!

Harkitaanpa samaa ongelmaa. On kellotapuli, jossa on 5 kelloa, ja sinulla on 8 kelloa. Juuri nyt et kuitenkaan halua selvittää kellojen järjestystä (muista, että se on permutaatio).

Sen sijaan haluat valita 5 parasta kelloa ja antaa jonkun toisen, jolla on parempi musiikkimaku, selvittää järjestyksen. Käytännössä hajotamme ongelman osiin: Ensin mietitään, mitkä kellot valitaan. Seuraavaksi mietitään, miten valitut kellot järjestetään.

Miten kellot valitaan? Tämä on ”yhdistelmä” permutaatioista ja yhdistelmästä.

Yhdistelmä on valinta. Sinä olet valikoiva. Valitset 5 kelloa niistä 8 kellosta, jotka käsityöläisesi ovat valmistaneet.

Koska tiedämme, miten kelloja tilataan, käytämme tätä tietoa selvittääksemme, miten kelloja valitaan. Kuulostaa mahdottomalta? Odota, kunnes näet siihen liittyvän kauniin matematiikan.

Kuvitellaan, että kaikki kellot ovat rivissä.

Ennen kuin keksimme kaikki tavat valita kellot, keskitytään yhteen tapaan valita kellot.

Yksi tapa on valita sattumanvaraisesti mitkä tahansa viisi. Tämä ei juurikaan auta meitä ratkaisemaan ongelmaa, joten kokeillaan toista tapaa.

Pannaan kellot riviin ja valitaan 5 ensimmäistä. Tämä on yksi tapa valita kellot.

Huomaa, että vaikka vaihdamme viiden ensimmäisen kellon paikkaa, valinta ei muutu. Ne ovat edelleen sama yksi tapa valita 5 ainutkertaista kelloa.

Tämä pätee myös kolmeen viimeiseen kelloon.

Nyt kaunis matemaattinen temppu – tämän yhden tavan valita 5 kelloa, mitkä ovat kaikki 8 kellon järjestykset, joissa valitsemme juuri nämä 5 kelloa? Yllä olevan kuvan perusteella se on kaikki 5 kellon järjestykset (5!) ja kaikki jäljelle jäävien kolmen kellon järjestykset (3!).

Siten jokaiselle ainoalle tavalle valita 5 kelloa meillä on (5! * 3!) 8 kellon järjestystä.

Mitkä ovat kaikki mahdolliset 8 kellon järjestykset? 8!.

Muistakaa, että jokaiselle 5 ensimmäisen kellon valinnalle meillä on (5! * 3!) 8 kellon järjestystä, jotka antavat saman valinnan.

Tällöin, jos kerromme 5 ensimmäisen kellon valintatapojen lukumäärän kaikilla yhden valinnan mahdollisilla järjestyksillä, meidän pitäisi saada järjestysten kokonaismäärä.

Ways to choose 5 bells * orderings of one choice = Total orderings

Siten,

Ways to choose 5 bells = the total possible orderings / total orderings of one choice.

Matemaattisesti siitä tulee:

(8 C 5) = 8! / ( 5! * 3!)

Kappas, olemme löytäneet intuitiivisen selityksen sille, miten valita 5 asiaa 8:sta.

Nyt voimme yleistää tämän. Jos meillä on N asiaa ja haluamme valita niistä R, se tarkoittaa, että vedämme viivan R:n kohdalle.

Jolloin jäljelle jäävät asiat ovat N-R. Yhdelle R esineiden valinnalle on siis R! * (N-R)! järjestystä, jotka antavat samat R esineet.

Kaikille tavoille valita R esinettä, meillä on N! / (R! * (N-R)!) mahdollisuutta.

Tapojen määrä valita r kohdetta n:sta on (n C r) = n! / (r! * (n-r)!)

Kielenkäytössä (n C r) lausutaan myös n choose r, mikä auttaa vakiinnuttamaan ajatuksen siitä, että kombinaatiot ovat kohteiden valitsemista varten.

Permutaatio – revisited

Kun kombinaatio on tehty ja pölyttömänä pois, palataan takaisin työhömme 2. osassa. Rakas ystävämme valitsi parhaat 5 kelloa selvittämällä kaikki mahdolliset 5 kellon yhdistelmät.

Tehtävämme on nyt löytää täydellinen melodia selvittämällä järjestysten määrä.

Mutta, tämä on helppo osuus. Tiedämme jo, miten tilata 5 kappaletta. Se on 5!, ja olemme valmiit.

Ja siis permutoidaksemme (järjestellaksemme) 5 kappaletta 8:sta, valitsemme ensin 5 kappaletta, ja sitten järjestelemme nämä 5 kappaletta.

Muilla sanoilla,

(8 P 5) = (8 C 5) * 5!

Ja jos laajennamme kaavaa, saadaan (8 P 5) = (8! / ( 5! * 3!)) * 5!

(8 P 5) = 8! / 3!.

Ja olemme päässeet täyteen ympyräämme alkuperäiseen kaavaamme, joka on johdettu oikein.

Tapojen määrä järjestää r elementtiä n:sta on (n P r) = n! / (n-r)!

Permutaation ja kombinaation ero

Toivottavasti tämä tekee permutaatioiden ja kombinaatioiden eron kristallinkirkkaaksi.

Permutaatiot ovat järjestyksiä, kun taas kombinaatiot ovat valintoja.

Järjestääksemme N:n alkuaineen järjestykseen löysimme vastauksen löytämiseen kaksi intuitiivista tapaa. Molemmat johtavat vastaukseen, N!.

Voidaksesi permutoida 5 elementtiä 8:sta, sinun on ensin valittava 5 elementtiä ja sitten järjestettävä ne. Valitaan käyttäen (8 C 5), sitten järjestetään 5 käyttäen 5!.

Ja intuitio R:n valitsemiseen N:sta on se, että lasketaan kaikki järjestykset (N!) ja jaetaan järjestyksillä, joissa ensimmäinen R ja viimeinen N-R pysyvät samoina (R! ja (N-R)!).

Ja siinä kaikki, mitä permutaatioissa ja yhdistelmissä on.

Jokainen kehittynyt permutaatio ja yhdistelmä käyttää tätä pohjana. Yhdistelmä, jossa on korvaus? Sama idea. Permutaatio identtisillä kohteilla? Sama idea, vain järjestysten määrä muuttuu, koska jotkut kohteet ovat identtisiä.

Jos kiinnostaa, voimme mennä monimutkaisiin tapauksiin toisessa esimerkissä. Kerro minulle Twitterissä.

Katso lisää postauksia blogissani ja liity viikoittaiselle postituslistalle.

Loppuhuomautukset

1. Näin kuvittelen, että hän selvitti asiat. Älkää pitäkö sitä historian oppituntina.
2. Intialaiset olivat 1200-luvulla 400 vuotta ennen häntä.