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

Соответственно, сочетания, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми — этим сочетания отличаются от размещений. Так, например, 3-элементные сочетания 2|1|3 и 3|2|1 ((нестрогие) подмножества, для которых ) из 6-элементного множества 1|2|3|4|5|6 () являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов 1|2|3.

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

Число сочетаний 

Число сочетаний из  по  равно биномиальному коэффициенту
 

При фиксированном  производящей функцией последовательности чисел сочетаний , , , … является
 

Двумерной производящей функцией чисел сочетаний является

Сочетания с повторениями 
Сочетанием с повторениями из  по  называется такой -элементный набор из -элементного множества, в котором каждый элемент может участвовать несколько раз, но в котором порядок не учитывается (мультимножество). В частности, число монотонных неубывающих функций из множества  в множество  равно числу сочетаний с повторениями из  по .

Число сочетаний с повторениями из  по  равно:
 

При фиксированном  производящая функция чисел сочетаний с повторениями из  по  равна
 

Двумерной производящей функцией чисел сочетаний с повторениями является

См. также 

 Комбинаторика
 Многочлен
 Мультиномиальный коэффициент
 Перестановка
 Размещение

Примечания

Ссылки 
 

Комбинаторика