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

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

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

3х элементные подмножества 5 элементного множества

Число сочетанийПравить

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

 

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

 

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

 

Сочетания с повторениямиПравить

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

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

 

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

 

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

 

См. такжеПравить

ПримечанияПравить

СсылкиПравить

  • Р. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990.