Сочетание

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Число сочетаний[править | править код]

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

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

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

Сочетания с повторениями[править | править код]

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

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

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

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

См. также[править | править код]

Примечания[править | править код]

Ссылки[править | править код]

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