Свойство сочетания что такое
Свойство сочетания что такое
Таким образом, полученные комбинации удовлетворяют различным условиям.
В зависимости от правил составления можно выделить три типа комбинаций: перестановки, размещения, сочетания.
Предварительно познакомимся с понятием факториала.
Произведение всех натуральных чисел от 1 до n включительно называют
Комбинация из n элементов, которые отличаются друг от друга только порядком элементов, называются перестановками.
Число перестановок можно вычислить по формуле
Запишем эту формулу в факториальной форме:
Кроме того, при решении задач используются следующие формулы, выражающие основные свойства сочетаний:
Наука собственными силами
Сочетания
Свойства сочетаний
Числа C k n обладают целым рядом замечательных свойств. Эти свойства можно доказать по-разному. Можно доказывать алгебраически – прямо воспользоваться формулой (8)
Но можно эти же свойства доказывать и чисто комбинаторными соображениями.
Свойствo 1
В формулу для C k n верхним индексом подставим (n-k). Получим
Однако намного изящнее комбинаторное доказательство:
Что значит «выбрать n-k предметов из n»? Это все равно что «указать k предметов, которые не будут выбраны». Т.е. выбрать n-k предметов из n можно столькими же способами, что и k предметов.
Этим свойством удобно пользоваться, когда верхний индекс ненамного меньше нижнего. Сравните, к примеру, два способа вычисления C 5 7:
напрямую используя формулу (8): 
или применяя формулу (9):
Не правда ли, второй проще?
Свойство 2
Запишем правую часть, используя формулу (8) для числа сочетаний:
Приведем к общему знаменателю, равному n!∙(n-k)!: 
Однако и здесь комбинаторное доказательство намного красивее:
Все сочетания из n по k (их количество равно C k n ) можно разбить на два класса: содержащие элемент под номером n и не содержащие его.
Выбрать из n элементов k штук, включая n-й – это все равно, что из оставшихся n-1 элементов выбрать k-1. Это можно сделать C k-1 n-1 способами.
Если же n-й элемент в сочетание не входит, то все k элементов нужно выбирать из оставшихся n-1 элементов. Это можно сделать C k n-1 способами.
Так как каждое сочетание из n по k входит или в один, или в другой класс, но не в оба сразу, можно применить правило суммы, и получить доказываемое равенство:
(10).
Свойство 3
В левой части равенства стоит количество всех сочетаний из n элементов (независимо от числа элементов в самих сочетаниях).
О каждом элементе мы можем принять решение: брать его в сочетание или не брать. Т.е. для каждого элемента есть два варианта решения: «да» и «нет». Будем для обозначения того или иного сочетания класть на каждый элемент монетку, причем «да» будем обозначать орлом, а «нет» – решкой. Таким образом, каждому сочетанию из n элементов будет соответствовать ряд из n монет. В разделе «Основные законы комбинаторики» мы доказали, что для n монет возможны 2n вариантов распределения орлов и решек. Поэтому количество всех сочетаний из n элементов равно 2n, что и требовалось доказать.
Перейти к следующей главе →