Сочетание
В комбинаторике сочетанием из по называется набор из элементов, выбранных из -элементного множества, в котором не учитывается порядок элементов.
Соответственно, сочетания, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми — этим сочетания отличаются от размещений. Так, например, 3-элементные сочетания 2 и 3 ((нестрогие) подмножества, для которых ) из 6-элементного множества 1 () являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов 1.
В общем случае число всех возможных -элементных подмножеств -элементного множества стоит на пересечении -й диагонали и -й строки треугольника Паскаля.[1]
Число сочетаний
[править | править код]Число сочетаний из по равно биномиальному коэффициенту
При фиксированном производящей функцией последовательности чисел сочетаний , , , … является
Двумерной производящей функцией чисел сочетаний является
Сочетания с повторениями
[править | править код]Сочетанием с повторениями из по называется такой -элементный набор из -элементного множества, в котором каждый элемент может участвовать несколько раз, но в котором порядок не учитывается (мультимножество). В частности, число монотонных неубывающих функций из множества в множество равно числу сочетаний с повторениями из по .
Число сочетаний с повторениями из по равно:
Пусть имеется типов объектов, причём объекты одного типа неотличимы. Пусть имеется неограниченное (или достаточно большое, во всяком случае, не меньше ) число объектов каждого типа. Из этого ассортимента выберем объектов; в выборке могут встречаться объекты одного типа, порядок выбора не имеет значения. Обозначим через число выбранных объектов -го типа, , . Тогда . Но число решений этого уравнения легко подсчитывается с помощью метода шаров и перегородок: каждое решение соответствует расстановке в ряд шаров и перегородок так, чтобы между -й и -й перегородками находилось ровно шаров. Но таких расстановок в точности , что и требовалось доказать.■
При фиксированном производящая функция чисел сочетаний с повторениями из по равна
Двумерной производящей функцией чисел сочетаний с повторениями является
См. также
[править | править код]Примечания
[править | править код]- ↑ Удивительный треугольник великого француза. Дата обращения: 20 апреля 2010. Архивировано 21 апреля 2010 года.