Permutaatio vs yhdistelmä: Mikä on ero permutaatiokaavan ja yhdistelmäkaavan välillä?

Tässä on lyhyt versio.

Otetaan esimerkkinä kirkon soittokellot.

Permutaatio on kellojen järjestys. Löydät parhaan järjestyksen soittaa heihin.

Yhdistelmä on kellojen valinta. Valitset kellot soimaan. Jos sinulla on liian monta kelloa, valitse ensin ne ja sitten miettiä niiden tilaamista.

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

Tilaamalla rtavarat ulos non ensin valita rtuotteet nja sitten tilata rtuotteet ( r!)

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

Mutta haluatko tietää, kuinka muistaa tämä ikuisesti?

Olen suuri ensimmäisten periaatteiden ajattelun fani. Ymmärtääksesi ongelman, mene sen ytimeen ja perustele sieltä ylöspäin.

Tämän tekemättä jättäminen aiheuttaa yleensä sekaannusta: jos en ymmärrä miten asiat toimivat, en tiedä mihin käsitteet ripustaa. Minun henkinen kehykseni ei ole täydellinen, joten päätän vain muistaa sen.

Kuten voitte kuvitella, tämä ei ole ihanteellinen. Joten, aika ajoin, hemmottelen itseäni harjoituksella, joka johtaa asioita lähteestä ja rakentaa intuitiota siitä, miten asiat toimivat.

Tällä kertaa rakennamme intuitiota permutaatioille ja yhdistelmille.

Esimerkiksi, tiedätkö miksi yhdistelmän kaava on (n C r)? Mistä tämä tuli? Ja miksi täällä käytetään faktoria?

Aloitetaan lähteestä. Factorials, Permutaatiot ja Yhdistelmät syntyivät yhdessä matematiikkojen kanssa, samoin kuin miten Steve Jobs ja Steve Wozniak perustivat Applen pelaamaan yhdessä autotallissaan.

Aivan kuten Applesta tuli täysimittainen kannattava yritys, yksinkertaisesta tekijästä !, tuli koko matemaattisen kentän atomi: kombinatorika.

Unohda kaikki, aloitetaan ajatteleminen alhaalta ylöspäin.

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

Oletko miettinyt, kuinka kelloja soitetaan kirkoissa? On kone, joka "soittaa" heitä järjestyksessä. Vaihdoimme koneisiin, koska kellot ovat liian suuria. Kelloja on myös tonnia.

Kuinka ihmiset selvittivät parhaan järjestyksen heitä soittamaan? Entä jos he haluaisivat vaihtaa asioita? Kuinka he löysivät parhaan äänen? Jokaisessa kellotornissa oli jopa 16 kelloa!

Et voinut muuttaa sitä, kuinka nopeasti voit soittaa kelloa - koneet soittivat vain yhden soittokellon sekunnissa. Ainoa mitä voit tehdä, oli muuttaa kellojen järjestystä. Joten tämä haaste koski parhaan järjestyksen selvittämistä.

Voisimmeko matkalla selvittää myös kaikki mahdolliset tilaukset? Haluamme tietää kaikki mahdolliset tilaukset selvittääksemme, kannattaako niitä kaikkia kokeilla.

Soittokello, Fabian Stedman, vastasi tähän haasteeseen.

Hän aloitti kahdella kellolla. Missä järjestyksissä hän voisi soittaa nämä kellot? [1]

1 ja 2.

tai

2 ja 1.

Tämä oli järkevää. Ei ollut muuta tapaa.

Entä 3 kelloa?

1, 2 ja 3.

1, 3 ja 2.

Aloita sitten toisella kellolla,

2, 1 ja 3.

2, 3 ja 1.

Aloita sitten kolmannesta kellosta,

3, 1 ja 2.

3, 2 ja 1.

Yhteensä 6.

Sitten hän tajusi, että tämä oli hyvin samanlainen kuin kaksi kelloa!

Jos hän kiinnitti ensimmäisen soittokellon, jäljellä olevien kahden kellon tilausmäärä oli aina kaksi.

Kuinka monella tavalla hän pystyi korjaamaan ensimmäisen kellon? Mikä tahansa kolmesta kellosta voisi olla yksi!

Okei, hän jatkoi. Sitten hän saavutti viisi kelloa.

Silloin hän huomasi, että asioiden tekeminen käsin on hankalaa. Sinulla on vain niin paljon aikaa päivässä, sinun on soitettava kelloja, et voi olla jumissa vetämällä kaikkia mahdollisia kelloja. Oliko tapa selvittää tämä nopeasti?

Hän palasi oivallukseensa.

Jos hänellä oli viisi kelloa ja hän kiinnitti ensimmäisen kellon, hänen tarvitsi vain selvittää, kuinka tilata neljä kelloa.

4 kelloa varten? No, jos hänellä oli neljä kelloa ja hän kiinnitti ensimmäisen kellon, hänen tarvitsi vain selvittää, kuinka tilata kolme kelloa.

Ja hän osasi tehdä tämän!

Joten 5 kellon tilaus = 5 * 4 kellon järjestys.

4 kellon järjestys = 4 * 3 kellon järjestys

Kolmen kellon järjestys = 3 * kahden kellon järjestys.

.. Näet kuvion, eikö niin?

Hauska tosiasia: Tämä on avain ohjelmointitekniikkaan, jota kutsutaan rekursioksi.

Hän teki niin. Vaikka se kesti paljon kauemmin, koska kukaan hänen lähistään ei ollut jo löytänyt tätä. [2]

Niinpä hän tajusi, että viiden kellon järjestys = 5 * 4 * 3 * 2 * 1.

Tämä tilauskaava, vuonna 1808, tuli tunnetuksi faktoriaalina.

Ajattelemme perustekijänä merkintöjä, mutta idea oli olemassa kauan ennen kuin sillä oli nimi. Vasta kun ranskalainen matemaatikko Christian Kramp huomasi sen käytön muutamassa paikassa, hän nimitti sen faktoriaaliksi.

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

Permutaatio on esineiden tilaaminen.

Kun opin jotain, mielestäni on hyödyllistä tarkastella asioita joka puolelta, vahvistaa ymmärrystä.

Entä jos yritämme johtaa yllä olevan kaavan suoraan yrittämättä vähentää ongelmaa pienempään kellojen määrään?

Meillä on 5 välilyöntiä, eikö?

Kuinka monella tapaa voimme valita ensimmäisen kellon? 5, koska se on kellojen lukumäärä.

Toinen kello? No, käytimme yhden kellon, kun asetimme sen ensimmäiseen asentoon, joten meillä on 4 kelloa jäljellä.

Kolmas kello? No, olemme valinneet kaksi ensimmäistä, joten jäljellä on vain 3 kelloa.

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

Viides kello? Vain 1 jäljellä, joten 1 vaihtoehto.

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

Siten meillä on ensimmäinen yleinen kaava.

Tavaroiden tilausmäärä Non N!

Permutaatio

Nyt kohtaamme toisen ongelman. Kuningas käski tehdä uusia kelloja jokaiselle kirkolle. Jotkut ovat mukavia, jotkut ovat kunnossa, jotkut saavat sinut kuuroon. Mutta jokainen on ainutlaatuinen. Jokainen antaa oman äänensä. Kuurova kello, jota ympäröivät mukavat kellot, voi kuulostaa majesteettiselta.

Kellotornissamme on kuitenkin vielä 5 kelloa, joten meidän on selvitettävä paras tilaus kahdeksasta kellosta, jotka ammattitaitoiset kellovalmistajat tekivät.

Edellä olevaa logiikkaa käyttämällä voimme jatkaa.

Ensimmäiselle kellolle voimme valita minkä tahansa 8 kellosta.

Toista kelloa varten voimme valita minkä tahansa jäljellä olevasta 7 kellosta ... ja niin edelleen.

Loppujen lopuksi saamme 8 * 7 * 6 * 5 * 4mahdolliset 8 kellon tilaukset 5 tilaan.

Jos tiedät kaavan (n P r) kaavaversiosta, toisin sanoen n! / (n-r)!, älä huoli, me johdamme sen myös tarpeeksi 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 tulemme sinne, katsotaanpa asioiden tai yhdistelmän valitseminen.

Yhdistelmä

Nyt kun tiedämme kuinka tilata asioita, voimme selvittää kuinka valita asiat!

Tarkastellaan samaa ongelmaa. Siellä on kellotorni, jossa on 5 kelloa, ja sinulla on 8 kelloa. Kuitenkin juuri nyt, et halua selvittää kellojen järjestystä (muista, että permutaatio on se).

Sen sijaan haluat valita viisi parasta kelloa ja antaa jonkun muun, jolla on parempi musiikkimaista, selvittää tilauksen. Itse asiassa jaamme ongelman osiin: Ensinnäkin selvitämme, mitkä kellot valita. Seuraavaksi selvitämme, kuinka tilata valitut kellot.

Kuinka valitset kellot? Tämä on "yhdistelmä" permutaatioista ja yhdistelmästä.

Yhdistelmä on valinta. Olet valikoiva. Valitset 5 kelloa käsityöläisten tekemästä kahdeksasta.

Koska tiedämme kuinka kelloja tilata, käytämme näitä tietoja selvittääkseen, kuinka kellot valitaan. Kuulostaa mahdottomalta? Odota, kunnes näet kauniin matematiikan.

Kuvitellaan, että kaikki kellot ovat linjassa.

Ennen kuin löydämme kaikki keinot kellojen valitsemiseksi, keskitytään yhteen tapaan valita kellot.

Yksi tapa on valita mikä tahansa 5 satunnaisesti. Tämä ei auta meitä ratkaisemaan ongelmaa paljon, joten yritetään toista tapaa.

Laitamme kellot riviin ja valitsemme ensimmäiset 5. Tämä on yksi tapa valita kellot.

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

Tämä pätee myös kolmelle viimeiselle kellolle.

Nyt kaunis matematiikkatemppu - mitkä ovat kaikki viisi kelloa tällä yhdellä tapalla valita 8 kelloa, joissa valitsemme juuri nämä 5 kelloa? Yllä olevasta kuvasta näet kaikki 5 kellon ( 5!) ja jäljellä olevien kolmen kellon ( 3!) järjestykset .

Siten jokaisella tapalla valita 5 kelloa meillä on ( 5! * 3!) tilauksia 8 kelloa.

Mitkä ovat 8 kellon mahdolliset tilaukset? 8!.

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

Jos kerrotaan sitten kuinka monta tapaa valita viisi ensimmäistä kelloa ja kaikki mahdolliset tilaukset yhdellä valinnalla, meidän pitäisi saada tilausten kokonaismäärä.

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

Niin,

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

Matematiikassa siitä tulee:

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

Katso, olemme löytäneet intuitiivisen selityksen kuinka valita 5 asiaa kahdeksasta.

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

Mikä tarkoittaa, että jäljellä olevat tuotteet ovat N-R. Joten yhdelle tuotevalinnalle Rmeillä on R! * (N-R)!tilauksia, jotka antavat samat Rtuotteet.

Kaikilla tavoilla valita Rtuotteita meillä on N! / (R! * (N-R)!)mahdollisuuksia.

Määrä tapoja valita rkohteita ulos nIS(n C r) = n! / (r! * (n-r)!)

Puhekielellä (n C r) lausutaan myös n choose r, mikä auttaa vahvistamaan ajatusta, että yhdistelmät ovat esineiden valitsemiseksi.

Permutaatio - tarkistettu

Kun yhdistelmä on tehty ja pölytetty, palataan takaisin työmme 2. osaan. Rakas ystävämme valitsi parhaat viisi kelloa selvittämällä kaikki mahdolliset 5 kellon yhdistelmät.

Meidän tehtävämme on nyt löytää täydellinen melodia selvittämällä tilausten määrä.

Mutta tämä on helppo pala. Tiedämme jo, kuinka tilata 5 tuotetta. Se on 5!, ja olemme valmiit.

Joten, jotta voimme muokata (tilata) 5 tuotetta 8: sta, valitsemme ensin 5 tuotetta ja sitten 5 tuotteet.

Toisin sanoen,

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

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

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

Ja olemme tulleet täydessä ympyrässä alkuperäiseen kaavaan, joka on johdettu oikein.

Kuinka monta tapaa tilata rtuotteita non(n P r) = n! / (n-r)!

Ero permutaation ja yhdistelmän välillä

Toivon, että tämä tekee eron permutaatioiden ja yhdistelmien välillä kristallinkirkkaaksi.

Permutaatiot ovat tilauksia, kun taas yhdistelmät ovat valintoja.

N elementin tilaamiseksi löysimme kaksi intuitiivista tapaa selvittää vastaus. Molemmat johtavat vastauksen, N!.

Jos haluat permutoida 5 elementtiä 8: sta, sinun on ensin valittava 5 elementtiä ja järjestettävä ne sitten. Valitset käyttämisen (8 C 5)ja tilaat sitten 5 5!.

Ja intuitio valita Rjoukosta Non mietitään kaikki orderings ( N!) ja jakamalla orderings jossa ensimmäinen Rja viimeinen N-Rovat samat ( R!ja (N-R)!).

Ja siinä on vain permutaatioita ja yhdistelmiä.

Jokainen edistynyt permutaatio ja yhdistelmä käyttää tätä perustana. Yhdistäminen vaihtoon? Sama idea. Permutaatio samanlaisten esineiden kanssa? Sama idea, vain tilausten määrä muuttuu, koska jotkut tuotteet ovat identtisiä.

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

Katso lisää viestejä blogissani ja liity viikoittaiseen postituslistalle.

Lopeta muistiinpanot

  1. Näin kuvittelen, että hän selvitti asiat. Älä ota sitä historian oppitunniksi.
  2. Intiaaneilla oli 1200-luvulla 400 vuotta ennen häntä.