В комбинаторике сочетанием из по называется набор элементов, выбранных из данного множества, содержащего различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
Так, например, наборы (3-х элементные сочетания, подмножества, ) {2, 1, 3} и {3, 2, 1} 6-ти элементного множества {1, 2, 3, 4, 5, 6} () являются одинаковыми (однако, как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.
В общем случае число, показывающее, сколькими способами можно выбрать элементов из множества, содержащего различных элементов, стоит на пересечении -й диагонали и -й строки треугольника Паскаля.[1]
Содержание |
Число сочетаний из по равно биномиальному коэффициенту
При фиксированном производящей функцией последовательности чисел сочетаний , , , … является:
Двумерной производящей функцией чисел сочетаний является
Сочетанием с повторениями называются наборы, в которых каждый элемент может участвовать несколько раз.
Число сочетаний с повторениями из по равно биномиальному коэффициенту
При фиксированном производящей функцией чисел сочетаний с повторениями из по является:
Двумерной производящей функцией чисел сочетаний с повторениями является:
Сочетание.