Просмотр кода страницы Сочетание

В [[комбинаторика|комбинаторике]] '''сочетанием''' из <math>n</math> по <math>k</math> называется набор из <math>k</math> элементов, выбранных из <math>n</math>-элементного [[множество|множества]], в котором не учитывается порядок элементов.

Соответственно, сочетания, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми — этим сочетания отличаются от [[размещение|размещений]]. Так, например, 3-элементные сочетания {{{Nums|2|1|3}}} и {{{Nums|3|2|1}}} ([[Подмножество#Определение|(нестрогие) подмножества]], для которых <math>k=3</math>) из 6-элементного множества {{{Nums|1|2|3|4|5|6}}} (<math>n=6</math>) являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов {{{Nums|1|2|3}}}.

В общем случае [[Сочетание#Число сочетаний|число]] всех возможных <math>k</math>-элементных подмножеств <math>n</math>-элементного множества стоит на пересечении <math>k</math>-й диагонали и <math>n</math>-й строки [[треугольник Паскаля|треугольника Паскаля]].<ref>{{Cite web |url=http://www.arbuz.uz/u_treug.html |title=Удивительный треугольник великого француза. |access-date=2010-04-20 |archive-date=2010-04-21 |archive-url=https://web.archive.org/web/20100421090559/http://arbuz.uz/u_treug.html |deadlink=no }}</ref>

[[Файл:Combinations without repetition; 5 choose 3.svg|thumb|200px|3-элементные подмножества 5-элементного множества]]

== Число сочетаний ==
{{main|Биномиальный коэффициент}}

'''Число сочетаний из <math>n</math> по <math>k</math>''' равно [[биномиальный коэффициент|биномиальному коэффициенту]]
: <math>{n\choose k} = C_n^k = \frac{n!}{k!\left(n-k\right)!}.</math>

При фиксированном <math>n</math> [[Производящая функция последовательности|производящей функцией]] последовательности чисел сочетаний <math>\tbinom{n}{0}</math>, <math>\tbinom{n}{1}</math>, <math>\tbinom{n}{2}</math>, … является
: <math>\sum_{k=0}^n \binom{n}{k} x^k = (1+x)^n.</math>

Двумерной производящей функцией чисел сочетаний является
: <math>\sum_{n=0}^{\infty} \sum_{k=0}^n \binom{n}{k} x^k y^n = \sum_{n=0}^{\infty} (1+x)^n y^n = \frac{1}{1-y-xy}.</math>

== {{anchor|Сочетания с повторениями}} Сочетания с повторениями ==
[[Файл:Combinations with repetitions choose 3 from 5.png|мини|300x300пкс|Иллюстрация]]
'''Сочетанием с повторениями''' из <math>n</math> по <math>k</math> называется такой <math>k</math>-элементный набор из <math>n</math>-элементного множества, в котором каждый элемент может участвовать несколько раз, но в котором порядок не учитывается ([[мультимножество]]). В частности, число [[Монотонная функция|монотонных]] неубывающих функций из множества <math>\{1,2,\dots,k\}</math> в множество <math>\{1,2,\dots,n\}</math> равно числу сочетаний с повторениями из <math>n</math> по <math>k</math>.

Число сочетаний с повторениями из <math>n</math> по <math>k</math> равно:
: <math>\overline{C^k_n}=C^k_{(n)}=\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{n-1} = \binom{n+k-1}{k} = (-1)^{k} \binom{-n}{k} = \frac{(n+k-1)!}{k!\cdot (n-1)!}.</math>

{{Доказ1|Пусть имеется <math>n</math> типов объектов, причём объекты одного типа неотличимы. Пусть имеется неограниченное (или достаточно большое, во всяком случае, не меньше <math>k</math>) число объектов каждого типа. Из этого ассортимента выберем <math>k</math> объектов; в выборке могут встречаться объекты одного типа, порядок выбора не имеет значения. Обозначим через <math>x_j</math> число выбранных объектов <math>j</math>-го типа, <math>x_j\geq 0</math>, <math>j=1,2,\dots,n</math>. Тогда <math>x_1+x_2+\dots+x_n=k</math>. Но число решений этого уравнения легко подсчитывается с помощью [[Метод шаров и перегородок|метода шаров и перегородок]]: каждое решение соответствует расстановке в ряд <math>k</math> шаров и <math>n-1</math> перегородок так, чтобы между <math>(j-1)</math>-й и <math>j</math>-й перегородками находилось ровно <math>x_j</math> шаров. Но таких расстановок в точности <math>\tbinom{n+k-1}{k}</math>, что и требовалось доказать.}}

При фиксированном <math>n</math> [[производящая функция последовательности|производящая функция]] чисел сочетаний с повторениями из <math>n</math> по <math>k</math> равна
: <math>\sum_{k=0}^{\infty}\left[(-1)^k {-n\choose k}\right] x^k = (1-x)^{-n}.</math>

Двумерной производящей функцией чисел сочетаний с повторениями является
: <math>\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} (-1)^k {-n\choose k} x^k y^n = \sum_{n=0}^{\infty} (1-x)^{-n} y^n = \frac{1-x}{1-x-y}.</math>

== См. также ==
{{навигация|Викисловарь=сочетание}}{{колонки}}
* [[Комбинаторика]]
* [[Многочлен]]
* [[Мультиномиальный коэффициент]]
* [[Перестановка]]
* [[Размещение]]
{{колонки|конец}}

== Примечания ==
{{примечания}}

== Ссылки ==
* {{книга | автор = {{нп4|Стенли, Ричард Питер|Стенли Р.||Richard P. Stanley}} |заглавие=Перечислительная комбинаторика |место={{М.}} |год=1990 |издательство=Мир}}
{{вс}}

[[Категория:Комбинаторика]]