Kā aprēķināt kombinācijas un permutācijas

Pieņemsim, ka jums ir n vienību veidi, un jūs vēlaties atlasīt to r kolekciju. Mēs varētu vēlēties šos priekšmetus noteiktā secībā. Mēs šos vienumu kopas saucam par permutācijām. Ja pasūtījumam nav nozīmes, kolekciju kopu mēs saucam par kombinācijām. Gan kombinācijām, gan permutācijām varat apsvērt gadījumu, kurā dažus no n veidiem izvēlaties vairāk nekā vienu reizi, ko sauc par “ar atkārtojumu”, vai gadījumu, kad katru veidu izvēlaties tikai vienu reizi, ko sauc par atkārtojums'. Mērķis ir spēt saskaitīt iespējamo kombināciju vai permutāciju skaitu konkrētajā situācijā.

Faktoriālo funkciju bieži izmanto, aprēķinot kombinācijas un permutācijas. N! ir N × (N – 1) ×... × 2 × 1. Piemēram, 5! = 5×4×3×2×1 = 120. Veidu skaits, kā pasūtīt priekšmetu komplektu, ir faktoriāls. Paņemiet trīs burtus a, b un c. Pirmajam burtam ir trīs izvēles iespējas, otrajam - divas un trešajam - tikai viena. Citiem vārdiem sakot, kopā 3 × 2 × 1 = 6 pasūtījumi. Kopumā ir n! veidi, kā pasūtīt n priekšmetus.

Pieņemsim, ka jums ir trīs istabas, kuras jūs krāsojat, un katra no tām tiks nokrāsota vienā no piecām krāsām: sarkana (r), zaļa (g), zila (b), dzeltena (y) vai oranža (o). Katru krāsu var izvēlēties tik reižu, cik vēlaties. Pirmajai istabai ir piecas krāsas, otrajā - piecas un trešajā - piecas. Tas kopā dod 5 × 5 × 5 = 125 iespējas. Parasti no n atkārtojamām izvēles veidiem, kā atlasīt r elementu grupu noteiktā secībā, ir n ^ r.

Tagad pieņemsim, ka katrai istabai būs atšķirīga krāsa. Pirmajai istabai varat izvēlēties no piecām krāsām, otrajā - četras un trešajā - tikai trīs. Tas dod 5 × 4 × 3 = 60, kas vienkārši ir 5! / 2!. Kopumā neatkarīgu veidu skaits, kā atlasīt r vienumus noteiktā secībā no n neatkārtojamām izvēlēm, ir n! / (N – r) !.

Pēc tam aizmirstiet, kura istaba ir kādā krāsā. Krāsu shēmai vienkārši izvēlieties trīs neatkarīgas krāsas. Kārtībai šeit nav nozīmes, tāpēc (sarkana, zaļa, zila) ir tāda pati kā (sarkana, zila, zaļa). Jebkurai trīs krāsu izvēlei ir 3! veidus, kā jūs varat tos pasūtīt. Tātad jūs samaziniet permutāciju skaitu par 3! lai iegūtu 5! / (2! × 3!) = 10. Parasti jūs varat izvēlēties r vienumu grupu jebkurā secībā no n neatkārtojamu izvēļu izvēles n! / [(N – r)! × r!] Veidos.

Visbeidzot, jums ir jāizveido krāsu shēma, kurā jūs varat izmantot jebkuru krāsu tik reižu, cik vēlaties. Gudrs grāmatvedības kods palīdz šim skaitīšanas uzdevumam. Izmantojiet trīs X, lai attēlotu telpas. Jūsu krāsu sarakstu attēlo “rgbyo”. Sajauciet Xs savā krāsu sarakstā un saistiet katru X ar pirmo krāsu pa kreisi no tā. Piemēram, rgXXbyXo nozīmē, ka pirmā istaba ir zaļa, otrā ir zaļa un trešā ir dzeltena. X ir jābūt vismaz vienai krāsai pa kreisi, tāpēc pirmajam X ir pieejamas piecas vietas. Tā kā sarakstā tagad ir X, otrajai X ir sešas pieejamās vietas un trešajai X ir septiņas. Kopumā ir 5 × 6 × 7 = 7! / 4! veidi, kā uzrakstīt kodu. Tomēr istabu secība ir patvaļīga, tāpēc patiešām ir tikai 7! / (4! × 3!) Unikālas kārtības. Parasti jūs varat izvēlēties r vienumus jebkurā secībā no n atkārtojamām izvēlēm (n + r – 1)! / [(N – 1)! × r!] Veidos.