Kombinációk és permutációk kiszámítása

Tegyük fel, hogy n típusú elemed van, és ki akarsz választani r gyűjteményt. Előfordulhat, hogy ezeket az elemeket bizonyos sorrendben kívánjuk megadni. Ezeket az elemkészleteket permutációknak nevezzük. Ha a sorrend nem számít, akkor a gyűjtemények kombinációját hívjuk. Mind a kombinációk, mind a permutációk esetében figyelembe veheti azt az esetet, amikor az n típus közül többet választ egyszer, amelyet „ismétléssel” hívnak, vagy az az eset, amikor az egyes típusokat csak egyszer választja, amelyet „nem” ismétlés'. A cél az, hogy képes legyen megszámolni az adott helyzetben lehetséges kombinációk vagy permutációk számát.

A faktoriális függvényt gyakran használják kombinációk és permutációk kiszámításakor. N! jelentése N × (N – 1) ×... × 2 × 1. Például 5! = 5×4×3×2×1 = 120. Az elemkészlet megrendelésének száma tényező. Vegyük a három a, b és c betűt. Három választási lehetősége van az első betűre, kettő a másodikra ​​és csak egy a harmadikra. Más szavakkal, összesen 3 × 2 × 1 = 6 megrendelés. Általában n vannak! n elem megrendelésének módjai.

Tegyük fel, hogy három szobája van, amelyeket festeni fog, és mindegyiket az öt szín egyikére festik: piros (r), zöld (g), kék (b), sárga (y) vagy narancs (o). Minden színt annyiszor kiválaszthat, ahányszor csak akarja. Öt szín közül választhat az első szobához, öt a másodikhoz és öt a harmadikhoz. Ez összesen 5 × 5 × 5 = 125 lehetőséget ad. Általánosságban elmondható, hogy n megismételhető választás közül egy adott sorrendben szereplő r elemek csoportjának kiválasztása n ^ r.

Tegyük fel, hogy minden szoba más színű lesz. Öt szín közül választhat az első szobához, négy a másodikhoz és csak három a harmadikhoz. Ez 5 × 4 × 3 = 60 értéket ad, ami véletlenül 5! / 2!. Általánosságban elmondható, hogy n megismételhetetlen választás közül az r elemek kiválasztása adott sorrendben n! / (N – r)!

Ezután felejtsd el, melyik szoba melyik színű. Csak válasszon három független színt a színvilághoz. A sorrend itt nem számít, tehát (piros, zöld, kék) megegyezik (piros, kék, zöld). Bármely három szín közül 3 választható! hogyan rendelheti meg őket. Tehát 3-mal csökkenti a permutációk számát! hogy 5! / (2! × 3!) = 10 legyen. Általában az r elemek csoportját tetszőleges sorrendben választhatja ki n megismételhetetlen választás közül n! / [(N – r)! × r!] Módon.

Végül létre kell hoznia egy színvilágot, amelyben bármilyen színt felhasználhat, ahányszor csak akar. Ügyes könyvelési kód segíti ezt a számlálási feladatot. Használjon három X-et a szobák ábrázolásához. A színlistát 'rgbyo' jelöli. Keverje össze az X-eket a színlistájába, és társítsa mindegyik X-et a tőle balra található első színhez. Például az rgXXbyXo azt jelenti, hogy az első szoba zöld, a második zöld, a harmadik sárga. Egy X-nek legalább egy színnel kell lennie balra, így öt szabad hely áll rendelkezésre az első X-hez. Mivel a listában most X szerepel, a második X-hez hat, a harmadik X-hez hét szabad hely tartozik. Összesen 5 × 6 × 7 = 7! / 4 van! a kód megírásának módjai. A szobák sorrendje azonban önkényes, így valójában csak 7! / (4! × 3!) Egyedi elrendezés létezik. Általában r elemeket tetszőleges sorrendben választhat n megismételhető választás közül (n + r – 1)! / [(N – 1)! × r!] Módon.