Сочетание

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Логотип Викисловаря
В Викисловаре есть статья «сочетание»

В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данного множества, содержащего n различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Так, например, наборы (3-элементные сочетания, подмножества, k=3) {2, 1, 3} и {3, 2, 1} 6-элементного множества {1, 2, 3, 4, 5, 6} (n=6) являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

В общем случае число, показывающее, сколькими способами можно выбрать k элементов из множества, содержащего n различных элементов, стоит на пересечении k-й диагонали и n-й строки треугольника Паскаля.[1]

Число сочетаний[править | править исходный текст]

Число сочетаний из n по k равно биномиальному коэффициенту

{n\choose k} = C_n^k = \frac{n!}{k!\left(n-k\right)!}.

При фиксированном n производящей функцией последовательности чисел сочетаний \tbinom{n}{0}, \tbinom{n}{1}, \tbinom{n}{2}, … является:

\sum_{k=0}^n \binom{n}{k} x^k = (1+x)^n.

Двумерной производящей функцией чисел сочетаний является

\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}.

Сочетания с повторениями[править | править исходный текст]

Сочетанием с повторениями называются наборы, в которых каждый элемент может участвовать несколько раз.

Число сочетаний с повторениями из n по k равно биномиальному коэффициенту

\binom{n+k-1}{n-1} = \binom{n+k-1}{k} = (-1)^{k} \binom{-n}{k} = \frac{(n+k-1)!}{k!\cdot (n-1)!}.

При фиксированном n производящей функцией чисел сочетаний с повторениями из n по k является:

\sum_{k=0}^{\infty} (-1)^k {-n\choose k} x^k = (1-x)^{-n}.

Двумерной производящей функцией чисел сочетаний с повторениями является:

\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}.

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]

  • Р. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990.