Сочетание

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

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

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

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

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

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

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

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

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

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

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


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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]

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