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