Сочетание: различия между версиями
Перейти к навигации
Перейти к поиску
imported>ПростаРечь Нет описания правки |
imported>MBH Нет описания правки |
||
| Строка 1: | Строка 1: | ||
В [[комбинаторика|комбинаторике]] '''сочетанием''' из <math>n</math> по <math>k</math> называется набор из <math>k</math> элементов, выбранных из <math>n</math>-элементного [[множество|множества]], в котором не учитывается порядок элементов. | |||
Соответственно, сочетания, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми — этим сочетания отличаются от [[размещение|размещений]]. Так, например, наборы букв латинского алфавита ABC и ACB представляют собой разные размещения, но одно и то же сочетание. | |||
{{ | В общем случае [[Сочетание#Число сочетаний|число]] всех возможных <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 |url-status=live }}</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 |издательство=Мир}} | ||
}} | {{вс}} | ||
[[Категория:Комбинаторика]] | |||
Текущая версия от 09:50, 8 ноября 2025
В комбинаторике сочетанием из <math>n</math> по <math>k</math> называется набор из <math>k</math> элементов, выбранных из <math>n</math>-элементного множества, в котором не учитывается порядок элементов.
Соответственно, сочетания, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми — этим сочетания отличаются от размещений. Так, например, наборы букв латинского алфавита ABC и ACB представляют собой разные размещения, но одно и то же сочетание.
В общем случае число всех возможных <math>k</math>-элементных подмножеств <math>n</math>-элементного множества стоит на пересечении <math>k</math>-й диагонали и <math>n</math>-й строки треугольника Паскаля<ref>Шаблон:Cite web</ref>.
Число сочетаний
Число сочетаний из <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 Сочетания с повторениями
Сочетанием с повторениями из <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>
При фиксированном <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>
См. также
Шаблон:НавигацияШаблон:Колонки