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