Permutatsioon vs kombinatsioon: mis vahe on permutatsioonivalemi ja kombinatsioonivalemi vahel?

Siin on lühike versioon.

Võtame näiteks kirikus helistavad kellad.

Permutatsioon on kellade järjestamine. Sa mõtled välja parima korralduse nende helistamiseks.

Kombinatsioon on kellade valik. Valite kellade helistamiseks. Kui teil on liiga palju kellasid, valiksite need kõigepealt ja mõtleksite siis nende tellimisele.

See tekitab tuttava identiteedi: (n P r) = (n C r) * r!

rÜksuste välja tellimise viis non kõigepealt valida rüksused välja nja seejärel tellida rüksused ( r!)

Ja see tähendab (n P r) = n! / (n-r)!ja(n C r) = n! / ( (n-r)! * r! )

Kuid kas soovite teada, kuidas seda igavesti meeles pidada?

Olen suur esimeste põhimõtete mõtlemise fänn. Probleemi mõistmiseks minge selle tuumani ja arutage sealt üles.

Selle tegemata jätmine tekitab tavaliselt segadust: kui ma ei saa aru, kuidas asjad käivad, ei tea ma, kuhu need mõisted riputada. Minu vaimne raamistik pole täielik, seega otsustan selle lihtsalt meelde jätta.

Nagu võite ette kujutada, pole see ideaalne. Niisiis, aeg-ajalt lasen end harjutada, et tuletada asju allikast ja luua intuitsiooni, kuidas asjad toimivad.

Seekord ehitame intuitsiooni permutatsioonide ja kombinatsioonide jaoks.

Näiteks, kas teate, miks kombinatsiooni valem on (n C r)? Kust see tuli? Ja miks kasutatakse siin faktoore?

Alustame allikast. Faktoorid, permutaadid ja kombinatsioonid sündisid koos matemaatikute mängimisel, umbes nagu see, kuidas Steve Jobs ja Steve Wozniak oma garaažis koos Apple'i asutasid.

Täpselt samamoodi, kuidas Apple'ist sai täieõiguslik kasumlik ettevõte, sai lihtsast faktooriumist !kogu matemaatika valdkonna aatom: kombinatorika.

Unusta kõik ära, hakkame mõtlema alt üles.

Esimene teadaolev huvitav kasutusjuht pärines kirikutelt 17. sajandil.

Kas olete mõelnud, kuidas kirikutes kellasid helistatakse? Seal on masin, mis "helistab" neile järjekorras. Me läksime üle masinatele, kuna kellad on liiga suured. Samuti on seal kellasid tonne.

Kuidas inimesed leidsid, milline on parim järjestus nende helistamiseks? Mis oleks, kui nad tahaksid asju ümber vahetada? Kuidas nad saaksid leida parima heli? Igas kellatornis oli kuni 16 kella!

Sa ei saanud muuta, kui kiiresti sa võisid kella helistada - masinad helistasid sekundis ainult ühe kella. Ainus asi, mida teha sai, oli kellade järjekorra muutmine. Nii et see väljakutse seisnes parima tellimuse väljaselgitamises.

Kas me saaksime teel olles teada ka kõik võimalikud tellimused? Tahame teada kõiki võimalikke tellimusi, et teada saada, kas tasub neid kõiki proovida.

Kellamees Fabian Stedman võttis selle väljakutse vastu.

Ta alustas 2 kellaga. Millises järjestuses ta neid kellukesi võiks helistada? [1]

1 ja 2.

või

2 ja 1.

See oli mõistlik. Muud moodi ei saanud.

Kuidas oleks 3 kellaga?

1, 2 ja 3.

1, 3 ja 2.

Seejärel alustades teisest kellast,

2, 1 ja 3.

2, 3 ja 1.

Seejärel alustades kolmandast kellast,

3, 1 ja 2.

3, 2 ja 1.

Kokku 6.

Seejärel sai ta aru, et see sarnaneb väga kahe kellaga!

Kui ta parandas esimese kella, siis ülejäänud kahe kella tellimise viiside arv oli alati kaks.

Mitu viisi suutis ta esimese kella parandada? Ükskõik milline kolmest kellast võiks olla üks!

Olgu, ta jätkas. Seejärel jõudis ta 5 kellani.

See on siis, kui ta mõistis, et asju käsitsi teha on kohmakas. Päeval on teil ainult nii palju aega, peate helistama kelladele, te ei saa jääda kinni kõigi võimalike kellade väljatõmbamiseks. Kas oli võimalik seda kiiresti aru saada?

Ta läks tagasi oma ülevaate juurde.

Kui tal oli 5 kella ja ta pani esimese kella korda, tuli tal vaid välja mõelda, kuidas 4 kella tellida.

4 kella jaoks? Noh, kui tal oli 4 kella ja ta pani esimese kella korda, tuli tal vaid välja mõelda, kuidas tellida 3 kella.

Ja ta oskas seda teha!

Niisiis, 5 kella tellimine = 5 * nelja kella tellimine.

4 kella tellimine = 4 * 3 kella tellimine

3 kella tellimine = 3 * kahe kella tellimine.

.. Näete mustrit, kas pole?

Lõbus fakt: see on rekursiooniks nimetatava programmeerimistehnika võti.

Ta tegi ka. Kuigi see võttis tal palju kauem aega, sest keegi tema läheduses polnud seda juba avastanud. [2]

Nii arvas ta, et 5 kella tellimine = 5 * 4 * 3 * 2 * 1.

Seda tellimisvalemit hakati 1808. aastal nimetama faktoriaaliks.

Me arvame, et aluseks on faktorite tähistamine, kuid idee eksisteeris juba ammu enne selle nime saamist. Alles siis, kui Prantsuse matemaatik Christian Kramp märkas selle kasutamist mõnes kohas, nimetas ta seda faktooriumiks.

Sellist kellade järjestust nimetatakse permutatsiooniks.

Permutatsioon on üksuste tellimine.

Midagi õppides aitab minu arvates asju vaadata iga erineva nurga alt, kinnistada arusaamist.

Mis oleks, kui prooviksime ülaltoodud valemi tuletada otse, püüdmata probleemi vähendada väiksemale kellade arvule?

Meil on 5 ruumi, eks?

Mitu viisi saame valida esimese kella? 5, sest see on kellade arv, mis meil on.

Teine kell? Noh, me kasutasime ühte kella, kui panime selle esimesele positsioonile, nii et meil on jäänud 4 kella.

Kolmas kell? Noh, me oleme valinud kaks esimest, nii et valida on jäänud ainult 3 kellukest.

Neljas kell? Ainult 2 kella on jäänud, seega 2 võimalust.

Viies kell? Ainult 1 on jäänud, seega 1 variant.

Ja meil on see olemas, tellimuste koguarv on 5 * 4 * 3 * 2 * 1

Seega on meil esimene üldvalem.

NÜksuste tellimise võimaluste arv on N!

Permutatsioon

Nüüd seisame silmitsi teise probleemiga. Kuningas käskis teha igale kirikule uued kellad. Mõni on tore, mõni okei, mõni paneb kurdiks. Kuid igaüks neist on ainulaadne. Igaüks teeb oma heli. Mõnusate kelladega ümbritsetud kõrvulukustav kell võib kõlada majesteetlikult.

Kuid meie kellatornis on endiselt viis kella, nii et peame välja selgitama 8 kellast parima tellimuse, mille oskuslikud kellategijad valmistasid.

Kasutades ülaltoodud loogikat, saame jätkata.

Esimese kella jaoks saame valida 8 kellast ükskõik millise.

Teiseks kellaks saame valida ülejäänud 7 kellast ükskõik millise ... ja nii edasi.

Lõpuks saame 8 * 7 * 6 * 5 * 4võimaliku 8 kella tellimuse 5 ruumis.

Kui olete tuttav (n P r) valemiversiooniga, see tähendab n! / (n-r)!, ärge muretsege, tuletame ka selle piisavalt kiiresti!

Üks halb viis selle tuletamiseks on nii lugeja kui nimetaja korrutamine 3-ga! meie ülaltoodud näites -

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

Kuid see ei aita meil mõista, miks see valem töötab. Enne kui sinna jõuame, vaatame asju või Kombinatsiooni.

Kombinatsioon

Nüüd, kui teame, kuidas asju tellida, saame aru, kuidas asju valida!

Vaatleme sama probleemi. Seal on 5 kellaga kellatorn ja teil on 8 kella. Kuid praegu ei taha te kellade järjekorda välja mõelda (pidage meeles, et see on permutatsioon).

Selle asemel soovite valida 5 parimat kellukest ja lasta kellelgi teisel parema muusikamaitsega tellimus välja mõelda. Tegelikult jagame probleemi osadeks: kõigepealt selgitame välja, millised kellad valida. Järgmisena selgitame välja, kuidas valitud kellad tellida.

Kuidas kellasid valida? See on "kombinatsioon" permutatsioonidest ja kombinatsioonist.

Kombinatsioon on valik. Olete valiv. Valite 5 kellukest kaheksast, mille teie käsitöölised on valmistanud.

Kuna teame, kuidas kellasid tellida, kasutame seda teavet kellade valimiseks. Tundub võimatu? Oodake, kuni näete kaunist matemaatikat.

Kujutame ette, et kõik kellad on reas.

Enne kõigi kellade valimise viiside leidmist keskendume ühele kellade valimise viisile.

Üks võimalus on valida suvaline 5 juhuslikult. See ei aita meil probleemi palju lahendada, seega proovime teist viisi.

Panime kellad ritta ja valime esimesed 5. See on üks kellade valimise viis.

Pange tähele, et isegi kui vahetame esimese 5 kella asukohta, ei muutu valik. Nad on ikka sama viis viisi unikaalse kella valimiseks.

See kehtib ka kolme viimase kella kohta.

Nüüd, ilus matemaatika trikk - selle ühe viisi valimiseks 5 kella, mis on kogu 8 kella järjestus, kus me valime täpselt need 5 kella? Ülaltoodud pildi järgi on see kõik viie kella ( 5!) ja ülejäänud kolme kella ( 3!) järjestused .

Seega, iga viisi jaoks, kuidas valida 5 kella, on meil ( 5! * 3!) tellimusi 8 kellast.

Kui palju on 8 kella võimalik kokku tellida? 8!.

Pidage meeles, et iga esimese viie kella valiku jaoks on meil ( 5! * 3!) tellitud 8 kella, mis annavad sama valiku.

Kui korrutame viie esimese kella valimise võimaluste arvu kõigi võimalike ühe valiku tellimustega, peaksime saama tellimuste koguarvu.

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

Niisiis,

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

Matemaatikas saab sellest:

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

Vaadake, me oleme leidnud intuitiivse selgituse, kuidas valida 5 asja 8 seast.

Nüüd võime seda üldistada. Kui meil on N asja ja me tahame neist valida R, tähendab see, et tõmbame R-le joone.

Mis tähendab, et järelejäänud esemed on N-R. Niisiis, ühe kaubavaliku jaoks on Rmeil R! * (N-R)!tellimused, mis annavad samad Resemed.

Kõigil Resemete valimise viisidel on meil N! / (R! * (N-R)!)võimalused.

rÜksuste valimise viiside arv non(n C r) = n! / (r! * (n-r)!)

Kõnekeeles hääldatakse ka (n C r) n choose r, mis aitab kinnistada ideed, et kombinatsioonid on üksuste valimiseks.

Permutatsioon - vaadatud uuesti

Kui kombinatsioon on tehtud ja tolmunud, tuleme tagasi oma töö 2. osa juurde. Meie kallis sõber valis välja viis parimat kellukest, selgitades välja kõik võimalikud viie kella kombinatsioonid.

Nüüd on meie ülesanne leida täiuslik meloodia, selgitades välja tellimuste arv.

Kuid see on lihtne asi. Me juba teame, kuidas tellida 5 eset. See on 5!ja me oleme valmis.

Nii et 5 elemendi kaheksast permutamiseks (tellimiseks) valime kõigepealt 5 üksust, seejärel tellime 5 üksust.

Teisisõnu,

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

Ja kui laiendame valemit, (8 P 5) = (8! / ( 5! * 3!)) * 5!

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

Ja oleme jõudnud ringiga oma algse valemi juurde, mis on õigesti tuletatud.

rÜksuste tellimise viiside arv non(n P r) = n! / (n-r)!

Permutatsiooni ja kombinatsiooni erinevus

Loodan, et see muudab permutatsioonide ja kombinatsioonide erinevuse kristallselgeks.

Permutatsioonid on järjestused, kombinatsioonid aga valikud.

N elemendi tellimiseks leidsime vastuse selgitamiseks kaks intuitiivset viisi. Mõlemad viivad vastuseni , N!.

Kaheksast elemendist 5 permutatsiooniks peate kõigepealt valima 5 elementi ja seejärel need tellima. Valite kasutamise (8 C 5)ja tellite seejärel 5 5!.

Ja intuitsiooni valides Rvälja Non figuring kõik orderings ( N!) ja jagades orderings kus esimene Rja viimane N-Rjääb samaks ( R!ja (N-R)!).

Ja see on kõik permutatsioonide ja kombinatsioonide jaoks.

Iga täiustatud permutatsioon ja kombinatsioon kasutab seda alusena. Kombineerimine asendamisega? Sama idee. Permutatsioon identsete esemetega? Sama idee, muutub ainult tellimuste arv, kuna mõned üksused on identsed.

Kui olete huvitatud, võime keerulisi juhtumeid käsitleda veel ühes näites. Andke mulle sellest teada Twitteris.

Vaadake veel minu blogi postitusi ja liituge iganädalase meililistiga.

Lõpunoodid

  1. Nii kujutan ette, kuidas ta asjad selgeks sai. Ärge võtke seda ajaloo õppetunnina.
  2. Indiaanlastel oli 12. sajandil enne teda 400 aastat.