Сочетание

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

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

[править] Явные формулы

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

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

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

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

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

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

[править] Сочетания с повторениями

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

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

{n+k-1\choose k} = (-1)^k {-n\choose k}.

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

\sum_{k=0}^n (-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.
  • Вычисление числа сочетаний онлайн
Источник — «http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5»