Kombinatsioonide ja permutaatide arvutamine

Oletame, et teil on n tüüpi üksusi ja soovite valida neist r kogumi. Võiksime soovida neid esemeid kindlas järjekorras. Nimetame neid üksuste komplekte permutatsioonideks. Kui tellimus pole oluline, kutsume kollektsioonide komplekti. Nii kombinatsioonide kui ka permutatsioonide puhul võite kaaluda juhtumit, mille puhul valite mõne n tüüpi rohkem kui üks kord, mida nimetatakse "kordusega", või juhtum, kus valite iga tüübi ainult üks kord, mida nimetatakse "ei" kordamine ”. Eesmärk on osata loendada antud olukorras võimalike kombinatsioonide või permutatsioonide arvu.

Kombinatsioonide ja permutatsioonide arvutamisel kasutatakse sageli faktoriaalfunktsiooni. N! tähendab N × (N – 1) ×... × 2 × 1. Näiteks 5! = 5×4×3×2×1 = 120. Üksuste komplekti tellimise viiside arv on faktoriaal. Võtke kolm tähte a, b ja c. Esimese tähe jaoks on teil kolm valikut, teise jaoks kaks ja kolmanda jaoks ainult üks valik. Teisisõnu kokku 3 × 2 × 1 = 6 tellimust. Üldiselt on n! n üksuse tellimise viise.

Oletame, et teil on kolm tuba, mida kavatsete värvida, ja igaüks neist värvitakse ühe viiest värvist: punane (r), roheline (g), sinine (b), kollane (y) või oranž (o). Iga värvi saate valida nii mitu korda kui soovite. Esimese toa jaoks on teil viis värvi, teise jaoks viis ja kolmanda jaoks viis värvi. See annab kokku 5 × 5 × 5 = 125 võimalust. Üldiselt on n korduva valiku hulgast konkreetses järjekorras r-i üksuste rühma valimise viis n ^ r.

Oletame, et igas toas saab olema erinev värv. Esimese toa jaoks saate valida viie värvi vahel, teise jaoks neli ja kolmanda jaoks kolm. See annab 5 × 4 × 3 = 60, mis on lihtsalt 5! / 2!. Üldiselt on n kordumatu valiku hulgast sõltumatute viiside kaupa r üksuste valimine kindlas järjekorras n! / (N – r) !.

Järgmisena unustage, milline tuba on mis värvi. Valige värviskeemi jaoks lihtsalt kolm iseseisvat värvi. Järjekord pole siin oluline, seega (punane, roheline, sinine) on sama mis (punane, sinine, roheline). Mis tahes kolme värvi valimisel on 3! kuidas saate neid tellida. Nii vähendate permutatsioonide arvu 3 võrra! saada 5! / (2! × 3!) = 10. Üldiselt saate n üksuse rida ükskõik millises järjekorras n kordumatute valikute hulgast n! / [(N – r)! × r!] Viisil.

Lõpuks peate looma värviskeemi, milles saate kasutada mis tahes värvi nii palju kordi kui soovite. Nutikas raamatupidamise kood aitab seda loendamisülesannet täita. Ruumide tähistamiseks kasutage kolme tähte X. Teie värvide loendit tähistab 'rgbyo'. Segage X-id oma värviloendisse ja seostage iga X esimese värviga sellest vasakul. Näiteks tähendab rgXXbyXo, et esimene tuba on roheline, teine ​​on roheline ja kolmas on kollane. X-il peab vasakul olema vähemalt üks värv, nii et esimese X jaoks on saadaval viis pesa. Kuna loendis on nüüd X, on teise X jaoks saadaval kuus pesa ja kolmanda X jaoks seitse. Kokku on neid 5 × 6 × 7 = 7! / 4! viise koodi kirjutamiseks. Tubade järjestus on aga meelevaldne, nii et unikaalseid korraldusi on tegelikult vaid 7! / (4! × 3!). Üldiselt võite valida n üksust järjestuses n korduva valiku hulgast (n + r – 1)! / [(N – 1)! × r!] Rühmas.