В комбинаторике сочетанием из по называется набор из элементов, выбранных из -элементного множества, в котором не учитывается порядок элементов.
Соответственно, сочетания, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми — этим сочетания отличаются от размещений. Так, например, наборы букв латинского алфавита ABC и ACB представляют собой разные размещения, но одно и то же сочетание.
В общем случае число всех возможных -элементных подмножеств -элементного множества стоит на пересечении -й диагонали и -й строки треугольника Паскаля.
Число сочетаний
Число сочетаний из по равно биномиальному коэффициенту
При фиксированном производящей функцией последовательности чисел сочетаний , , , … является
Двумерной производящей функцией чисел сочетаний является
Свойства сочетаний
Симметрия
Выбор элементов из равносилен выбору элементов, которые не войдут в подмножество. Следует непосредственно из формулы, так как при замене на числитель не меняется, а два множителя знаменателя меняются местами.
Рекуррентное соотношение (правило Паскаля)
Это правило лежит в основе построения треугольника Паскаля. Каждый элемент равен сумме двух элементов, стоящих над ним. Из элементов можно выбрать либо включив фиксированный элемент (тогда остаётся выбрать из оставшихся ), либо не включив его (тогда выбираем из ).
Сумма всех сочетаний
Вытекает из бинома Ньютона при : . Суммарное число всех подмножеств -элементного множества, включая пустое, равно .
Знакочередующаяся сумма
Вытекает из бинома Ньютона при : . Следовательно, число подмножеств с чётным числом элементов равно числу подмножеств с нечётным числом элементов и каждое из этих чисел равно .
Свойство поглощения
или, эквивалентно, . Проверяется прямым раскрытием через факториалы и удобно для упрощения выражений, содержащих произведения числа сочетаний на множитель.
Сумма квадратов
Частный случай тождества Вандермонда. Число способов выбрать элементов из можно подсчитать, разбив множество на две равные половины и перебрав все возможные распределения выбора между ними: , а по свойству симметрии .
Тождество «хоккейной клюшки»
Название связано с геометрической интерпретацией в треугольнике Паскаля. Диагональный столбец слагаемых и результат образуют фигуру, напоминающую хоккейную клюшку. Доказывается индукцией по с использованием правила Паскаля.
Максимальное значение Биномиальные коэффициенты при фиксированном возрастают с ростом до середины и убывают после неё (в силу свойства симметрии): если чётно, единственный максимум достигается при ; если нечётно, максимум достигается при и , причём оба значения равны.
Сочетания с повторениями
Сочетанием с повторениями из по называется такой -элементный набор из -элементного множества, в котором каждый элемент может участвовать несколько раз, но в котором порядок не учитывается (мультимножество). В частности, число монотонных неубывающих функций из множества в множество равно числу сочетаний с повторениями из по .
Число сочетаний с повторениями из по равно:
При фиксированном производящая функция чисел сочетаний с повторениями из по равна
Двумерной производящей функцией чисел сочетаний с повторениями является
См. также
Комбинаторика Многочлен Мультиномиальный коэффициент Перестановка Размещение
Треугольник Паскаля
Примечания
Литература
Ссылки
Категория:Комбинаторика