Как да изчислим комбинации и пермутации

Да предположим, че имате n вида елементи и искате да изберете колекция от r от тях. Може да искаме тези артикули в определен ред. Ние наричаме тези набори от елементи пермутации. Ако редът няма значение, извикваме набора от комбинации от колекции. Както за комбинации, така и за пермутации, можете да разгледате случая, в който сте избрали някои от n типа повече от веднъж, което се нарича „с повторение“ или случаят, в който избирате всеки тип само веднъж, което се нарича „не повторение “. Целта е да можете да преброите възможния брой комбинации или пермутации в дадена ситуация.

Функцията факториал често се използва при изчисляване на комбинации и пермутации. Н! означава N × (N – 1) ×... × 2 × 1. Например 5! = 5×4×3×2×1 = 120. Броят на начините за поръчване на набор от артикули е факториален. Вземете трите букви a, b и c. Имате три възможности за избор на първата буква, две за втората и само една за третата. С други думи, общо 3 × 2 × 1 = 6 поръчки. Като цяло има n! начини за поръчка на n артикули.

Да предположим, че имате три стаи, които ще рисувате, и всяка от тях ще бъде боядисана в един от петте цвята: червен (r), зелен (g), син (b), жълт (y) или оранжев (o). Можете да изберете всеки цвят колкото пъти искате. Имате пет цвята за избор за първата стая, пет за втората и пет за третата. Това дава общо 5 × 5 × 5 = 125 възможности. Като цяло броят на начините за избор на група от r елементи в определен ред от n повторяеми избора е n ^ r.

Сега да предположим, че всяка стая ще бъде с различен цвят. Можете да изберете от пет цвята за първата стая, четири за втората и само три за третата. Това дава 5 × 4 × 3 = 60, което просто е 5! / 2!. По принцип броят на независимите начини за избор на r елементи в определен ред от n неповторими избора е n! / (N – r) !.

След това забравете коя стая е кой цвят. Просто изберете три независими цвята за цветовата схема. Тук редът няма значение, така че (червено, зелено, синьо) е същото като (червено, синьо, зелено). За всеки избор от три цвята има 3! начини, по които можете да ги поръчате. Така че намалявате броя на пермутациите с 3! за да получите 5! / (2! × 3!) = 10. Като цяло можете да изберете група от r елементи във произволен ред от селекция от n неповторими избора по n! / [(N – r)! × r!] Начини.

И накрая, трябва да създадете цветова схема, в която можете да използвате всеки цвят толкова пъти, колкото искате. Умен счетоводен код помага на тази задача за преброяване. Използвайте три X, за да представите стаите. Списъкът ви с цветове е представен от 'rgbyo'. Смесете Xs във вашия цветен списък и свържете всеки X с първия цвят вляво от него. Например rgXXbyXo означава, че първата стая е зелена, втората е зелена и третата е жълта. X трябва да има поне един цвят вляво, така че има пет налични слота за първия X. Тъй като списъкът вече включва X, има шест налични слота за втория X и седем налични слота за третия X. Като цяло има 5 × 6 × 7 = 7! / 4! начини за писане на кода. Редът на стаите обаче е произволен, така че наистина има само 7! / (4! × 3!) Уникални аранжировки. Като цяло можете да изберете r елементи във всякакъв ред от n повторяеми избора по (n + r – 1)! / [(N – 1)! × r!] Начини.