Комбинаторные алгоритмы для программистов



             

Сочетания


В тех случаях, когда нас не интересует порядок элементов в комбинации, а интересует лишь ее состав, говорят о сочетаниях. Итак,

k
-сочетаниями из
n

элементов называют всевозможные

k
- расстановки, составленные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов. Число
k
-сочетаний, которое можно составить из
n
элементов, обозначают через
C_n^k
.

Формула для числа сочетаний получается из формулы для числа размещений. В самом деле, составим сначала все

k
-сочетания из
n

элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получается, что все

k
-размещения из
n
элементов, причем каждое только по одному разу. Но из каждого
k
- сочетания можно сделать
k!
перестановок, а число этих сочетаний равно
C_n^k
. Значит справедлива формула
k!C_n^k = A_n^k.
Из этой формулы находим, что
C_n^k = \frac{{A_n^k }}{{k!}} = \frac{{n!}}{{(n - k)!k!}}.




Содержание  Назад  Вперед