Permutacija vs kombinacija: koks skirtumas tarp Permutacijos formulės ir Kombinacijos formulės?

Štai trumpa versija.

Kaip pavyzdį paimkime bažnyčios varpų skambėjimą.

Permutacija yra varpų eiliškumas. Išsiaiškinate, kokia geriausia tvarka juos paskambinti.

Derinys yra varpų pasirinkimas. Jūs renkatės skambučius. Jei turite per daug varpų, pirmiausia juos turėtumėte pasirinkti, o tada pagalvokite apie jų užsakymą.

Tai sukuria pažįstamą tapatybę: (n P r) = (n C r) * r!

Būdas užsakymų rdaiktų iš nyra pirmasis pasirinkti relementus iš n, tada užsisakyti relementus ( r!)

Tai reiškia (n P r) = n! / (n-r)!ir(n C r) = n! / ( (n-r)! * r! )

Bet ar norite žinoti, kaip tai prisiminti amžinai?

Aš esu didelis pirmųjų principų gerbėjas. Norėdami suprasti problemą, įsigilinkite į jos esmę ir paaiškinkite iš ten.

Tai nedarant dažniausiai kyla painiava: jei nesuprantu, kaip viskas veikia, nežinau, kur pakabinti sąvokas. Mano psichinė sistema nėra išsami, todėl nusprendžiu ją tiesiog prisiminti.

Kaip galite įsivaizduoti, tai nėra idealu. Taigi kartas nuo karto pasiduodu pratyboms, kad išgaunčiau daiktus iš šaltinio ir kurčiau intuiciją, kaip viskas veikia.

Šį kartą mes kuriame intuiciją apie permutacijas ir derinius.

Pavyzdžiui, ar žinote, kodėl derinio formulė yra (n C r)? Iš kur tai atsirado? Ir kodėl čia naudojami faktorialai?

Pradėkime nuo šaltinio. Faktorai, „Permutacijos“ ir „Deriniai“ gimė matematikams žaidžiant kartu, panašiai kaip Steve'as Jobsas ir Steve'as Wozniakas įkūrė „Apple“, kartu žaidžiantį savo garaže.

Lygiai taip pat, kaip „Apple“ tapo visaverte pelningąja įmone, paprastas faktorialas !, tapo visos matematikos srities - kombinatorikos - atomu.

Pamiršk viską, pradėkime galvoti iš apačios į viršų.

Pirmasis žinomas įdomus naudojimo atvejis kilo iš Bažnyčių XVII a.

Ar susimąstėte, kaip bažnyčiose skamba varpai? Yra mašina, kuri juos „žieduoja“ tvarkingai. Mes perėjome prie mašinų, nes varpai per dideli. Be to, yra daugybė varpų.

Kaip žmonės išsiaiškino geriausią jų skambėjimo seką? Kas būtų, jei jie norėtų viską pakeisti? Kaip jie galėjo rasti geriausią garsą? Kiekvienoje varpinėje buvo iki 16 varpų!

Negalėjai pakeisti, kaip greitai galėtum paskambinti - mašinos kas sekundę skambindavo tik po vieną varpą. Vienintelis dalykas, kurį galėjai padaryti, buvo pakeisti varpų tvarką. Taigi, šis iššūkis buvo išsiaiškinti geriausią užsakymą.

Ar galėtume kelyje sužinoti ir visus galimus užsakymus? Norime sužinoti visus įmanomus užsakymus, kad išsiaiškintume, ar verta juos visus išbandyti.

Varpininkas Fabianas Stedmanas priėmė šį iššūkį.

Jis pradėjo nuo 2 varpų. Kokia tvarka jie galėtų skambinti šiais varpais? [1]

1 ir 2.

arba

2 ir 1.

Tai buvo prasminga. Kito kelio nebuvo.

Kaip su 3 varpais?

1, 2 ir 3.

1, 3 ir 2.

Tada pradedant antruoju varpu,

2, 1 ir 3.

2, 3 ir 1.

Tada pradedant trečiuoju varpu,

3, 1 ir 2.

3, 2 ir 1.

Iš viso 6.

Tada jis suprato, kad tai labai panašu į du varpus!

Jei jis sutvarkė pirmąjį skambutį, tada likusių dviejų varpų užsakymo būdų skaičius visada buvo du.

Kiek būdų jis galėjo sutvarkyti pirmąjį varpą? Bet kuris iš 3 varpų gali būti vienas!

Gerai, jis tęsė. Tada jis pasiekė 5 varpus.

Tai yra tada, kai jis suprato, kad viską daryti rankomis yra nepatogu. Jūs turite tik tiek laiko dieną, jūs turite skambinti varpais, jūs negalite būti įstrigę, ištraukdami visus galimus varpus. Ar buvo būdas greitai tai išsiaiškinti?

Jis grįžo prie savo įžvalgos.

Jei jis turėjo 5 varpus ir sutvarkė pirmąjį skambutį, jam tereikėjo sugalvoti, kaip užsisakyti 4 varpus.

4 varpams? Na, jei jis turėjo 4 varpus ir sutaisė pirmąjį skambutį, jam tereikėjo sugalvoti, kaip užsisakyti 3 varpus.

Ir jis žinojo, kaip tai padaryti!

Taigi, 5 varpų užsakymas = 5 * 4 varpų užsakymas.

4 varpų užsakymas = 4 * 3 varpų užsakymas

3 varpų užsakymas = 3 * 2 varpų užsakymas.

.. Jūs matote modelį, ar ne?

Įdomus faktas: tai yra programavimo technikos, vadinamos rekursija, raktas.

Jis taip pat padarė. Nors tai užtruko daug ilgiau, nes niekas šalia jo dar nebuvo to atradęs. [2]

Taigi jis suprato, kad 5 varpų užsakymas = 5 * 4 * 3 * 2 * 1.

Ši 1808 m. Užsakymo formulė buvo žinoma kaip faktorialas.

Mes galvojame apie faktorių žymėjimą kaip pagrindą, tačiau idėja egzistavo ilgai, kol ji dar neturėjo pavadinimo. Tik kai prancūzų matematikas Christianas Krampas pastebėjo, kad jis buvo naudojamas keliose vietose, jis pavadino jį faktoriumi.

Šis varpų užsakymas vadinamas permutacija.

Permutacija yra daiktų užsakymas.

Kai ko išmokau, manau, kad tai padeda pažvelgti į dalykus visais kitais kampais, sustiprinti supratimą.

Ką daryti, jei mes bandytume išvesti aukščiau pateiktą formulę tiesiogiai, nebandydami sumažinti problemos iki mažesnio varpų skaičiaus?

Mes turime 5 vietas, tiesa?

Kiek būdų galime pasirinkti pirmąjį varpą? 5, nes tiek varpų turime.

Antras varpas? Na, mes panaudojome vieną varpą, kai pastatėme jį į pirmąją poziciją, taigi mums liko 4 varpai.

Trečias varpas? Na, mes pasirinkome pirmuosius du, todėl liko tik 3 varpai.

Ketvirtasis varpas? Liko tik 2 varpai, taigi 2 variantai.

Penktasis varpas? Liko tik 1, taigi 1 variantas.

Ir mes turime, bendras užsakymų skaičius yra 5 * 4 * 3 * 2 * 1

Taigi, mes turime savo pirmąją bendrą formulę.

Prekių užsakymo būdų skaičius Nyra N!

Permutacija

Dabar susiduriame su kita problema. Karalius įsakė pagaminti naujus varpus kiekvienai bažnyčiai. Kai kurie yra malonūs, kai kurie yra gerai, kai kurie privers jus apkursti. Bet kiekvienas yra unikalus. Kiekvienas skleidžia savo garsą. Kurtinantis varpas, apsuptas gražių varpų, gali skambėti didingai.

Tačiau mūsų varpinėje vis dar yra 5 varpai, todėl turime išsiaiškinti geriausią užsakymą iš 8 varpų, kuriuos pagamino kvalifikuoti varpų gamintojai.

Naudodamiesi minėta logika, galime tęsti.

Pirmajam varpui galime pasirinkti bet kurį iš 8 varpų.

Antram varpui galime pasirinkti bet kurį iš likusių 7 varpų ... ir pan.

Galų gale mes gauname 8 * 7 * 6 * 5 * 4galimus 8 varpų užsakymus 5 vietose.

Jei esate susipažinę su formulės (n P r) versija, tai yra n! / (n-r)!, nesijaudinkite, mes tai taip pat išvesime pakankamai greitai!

Vienas blogas būdas tai išgauti - padauginti skaitiklį ir vardiklį iš 3! aukščiau pateiktame pavyzdyje -

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

Bet tai mums nepadeda suprasti, kodėl ši formulė veikia. Prieš ten nuvykdami, pažvelkime į daiktų pasirinkimą arba derinį.

Kombinacija

Dabar, kai mokame užsakyti daiktus, galime išsiaiškinti, kaip išsirinkti daiktus!

Apsvarstykime tą pačią problemą. Yra varpinė su 5 varpais, o jūs turite 8 varpus. Tačiau šiuo metu nenorite išsiaiškinti varpų tvarkos (atminkite, kad tai yra permutacija).

Vietoj to, jūs norite pasirinkti 5 geriausius varpus ir leisti kitam, turinčiam geresnį muzikos skonį, išsiaiškinti užsakymą. Iš tikrųjų mes išskaidome problemą į dalis: pirmiausia išsiaiškiname, kuriuos varpus pasirinkti. Toliau mes išsiaiškiname, kaip užsisakyti pasirinktus varpus.

Kaip pasirenkate varpus? Tai yra „derinys“ iš permutacijų ir derinių.

Derinys yra pasirinkimas. Tu esi atrankus. Iš 8 meistrų pagamintų varpų renkatės 5.

Kadangi mes žinome, kaip užsisakyti varpus, mes naudosime šią informaciją norėdami sužinoti, kaip pasirinkti varpus. Skamba neįmanoma? Palaukite, kol pamatysite gražią matematiką.

Įsivaizduokime, visi varpai yra vienoje linijoje.

Prieš rasdami visus varpų pasirinkimo būdus, susitelkime į vieną būdą, kaip pasirinkti varpus.

Vienas iš būdų yra pasirinkti bet kurį 5 atsitiktinai. Tai mums nelabai padeda išspręsti problemą, todėl išbandykime kitą būdą.

Varpus dedame į eilę ir pasirenkame pirmuosius 5. Tai vienas iš būdų pasirinkti varpus.

Atkreipkite dėmesį, kad net jei mes pakeičiame pirmųjų 5 varpų padėtį, pasirinkimas nesikeičia. Jie vis tiek yra tas pats būdas pasirinkti 5 unikalius varpus.

Tai galioja ir paskutiniams trims varpams.

Dabar gražus matematikos triukas - koks yra 5 varpų išsirinkimo būdas, kai mes pasirenkame būtent tuos 5 varpus? Iš aukščiau esančio paveikslėlio pateikiami visi 5 varpų ( 5!) ir likusių trijų varpų ( 3!) užsakymai .

Taigi kiekvienam 5 varpų pasirinkimo būdui turime ( 5! * 3!) 8 varpų užsakymus.

Kokie galimi 8 varpų užsakymai? 8!.

Atminkite, kad kiekvienam 5 pirmųjų varpų pasirinkimui turime ( 5! * 3!) 8 varpų užsakymus, kurie suteikia tą patį pasirinkimą.

Tada, jei padauginsime pirmųjų 5 varpų pasirinkimo būdų skaičių su visais galimais vieno pasirinkimo užsakymais, turėtume gauti bendrą užsakymų skaičių.

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

Taigi,

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

Matematikoje tai tampa:

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

Štai, mes radome intuityvų paaiškinimą, kaip pasirinkti 5 dalykus iš 8.

Dabar galime tai apibendrinti. Jei turime N daiktus ir norime pasirinkti iš jų R, tai reiškia, kad ties R nubrėžiame liniją.

O tai reiškia, kad likę daiktai bus N-R. Taigi, norint pasirinkti vieną Rdaiktą, turime R! * (N-R)!užsakymų, kurie suteikia tas pačias Rprekes.

Visais būdais pasirinkti Rdaiktus mes turime N! / (R! * (N-R)!)galimybių.

rElementų pasirinkimo būdų skaičius nyra(n C r) = n! / (r! * (n-r)!)

Šnekamojoje kalboje taip pat tariamas (n C r) n choose r, kuris padeda įtvirtinti mintį, kad deriniai yra skirti daiktams pasirinkti.

Permutacija - peržiūrėta

Atlikę derinį ir nuvalę dulkes, grįžkime prie savo darbo 2 dalies. Mūsų brangus draugas išrinko geriausius 5 varpus, suprasdamas visus galimus 5 varpų derinius.

Dabar mūsų darbas yra surasti tobulą melodiją, apskaičiuojant užsakymų skaičių.

Bet tai yra lengvas dalykas. Mes jau žinome, kaip užsisakyti 5 daiktus. Tai 5!ir mes baigėme.

Taigi, norėdami permutuoti (užsisakyti) 5 elementus iš 8, mes pirmiausia pasirenkame 5 elementus, tada užsakome 5 elementus.

Kitaip tariant,

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

Jei išplėsime formulę, (8 P 5) = (8! / ( 5! * 3!)) * 5!

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

Ir mes priėjome visą ratą prie savo pradinės formulės, tinkamai išvestos.

Iš būdais skaičius užsakymo rdaiktų iš nYRA(n P r) = n! / (n-r)!

Skirtumas tarp permutacijos ir derinio

Tikiuosi, kad dėl to skirtumas tarp permutacijų ir derinių bus visiškai aiškus.

Permutacijos yra užsakymai, o deriniai yra pasirinkimai.

Norėdami užsisakyti N elementus, radome du intuityvius būdus atsakymui išsiaiškinti. Abi lemia atsakymą N!.

Norėdami permutuoti 5 iš 8 elementų, pirmiausia turite pasirinkti 5 elementus, tada juos užsisakyti. Pasirenkate naudoti (8 C 5), tada užsisakykite 5 naudodami 5!.

Pasirinkimo Riš intuicija Nyra išsiaiškinti visas tvarkas ( N!) ir padalyti iš eilės, kur pirmasis Rir paskutinis N-Rlieka tie patys ( R!ir (N-R)!).

Viskas, kas yra permutacijos ir deriniai.

Kiekvienas išplėstinis permutavimas ir derinys tai naudoja kaip pagrindą. Derinys su pakeitimu? Ta pati idėja. Permatacija su identiškais daiktais? Ta pati idėja, keičiasi tik užsakymų skaičius, nes kai kurios prekės yra tapačios.

Jei jus domina, galime nagrinėti sudėtingus atvejus kitame pavyzdyje. Praneškite man „Twitter“.

Peržiūrėkite daugiau įrašų mano tinklaraštyje ir prisijunkite prie savaitinio adresų sąrašo.

Pabaigos užrašai

  1. Taip įsivaizduoju, kad jis viską suprato. Negalima to laikyti istorijos pamoka.
  2. Indai XII amžiuje turėjo 400 metų prieš jį.