Df. Сочетаниями называются различные подмножества заданной численности некоторого исходного множества. Численность выбираемого подмножества r называется размером (или объемом) выборки.
# Пусть множество . Образуем из него различные подмножества выбирая по два элемента. Получим множество сочетаний
.
Пусть V — первичное множество, содержащее n=n (V) элементов, а r — численность каждого из образуемых подмножеств. Число r будем называть размером выборки. Очевидно, что r — целое число: 0£ r £ n.
Количество сочетаний обозначают (читают «цэ из эн по эр»)[1].
Теорема. Число сочетаний равно факториалу численности множества, деленному факториал размера одной выборки и на факториал размера ее дополнения.
(10) .
Для упрощения рассуждений используем множество V = {1; 2; …; n } в качестве первичного. Каждое сочетание взаимно однозначно можно зашифровать двоичным индексным кодом длиной n символов (см. доказательство теоремы о численности булеана). Например: код 11100…0 соответствует сочетанию {1; 2; 3}, код 10110…0 — {1; 3; 4}.
|
|
Количество сочетаний равно количеству соответствующих кодов.
Все используемые коды содержат r единиц и n–r нулей, а количество таких кодов равно искомому числу сочетаний. Данные коды различаются только последовательностью единиц и нулей. Значит, они могут быть сосчитаны как перестановки с повторениями. Тогда
.
Пример. Назначение трех дежурных из 24 учащихся класса.
Пусть учитель назначил Иванова, Петрова и Сидорова. Переставляя эти три фамилии, мы получим шесть различных размещений. Однако в данной задаче нам безразлично, в каком порядке дежурные перечислены. В любом из этих вариантов дежурят те же трое.
Обозначим количество сочетаний из n элементов по k символом . Из примера видно, что каждой неупорядоченной выборке k элементов отвечает Pk различныхразмещений:
.
Отсюда искомое число сочетаний равно
. (7)
В приведенном примере дежурных можно назначить
способами.
Df. Размещениями называют упорядоченные подмножества, содержащие заданное число r элементов некоторого первичного множества.
Очевидно, что размер выборки r — целое число, не превосходящее численность первичного множества n: 0£ r £ n. Количество размещений обозначают (читают «а из эн по эр»)[2].
# Пусть множество . Образуем из него различные упорядоченные выборки по два элемента. Получим множество размещений
.
Теорема. Число размещений равно факториалу численности множества, деленному на факториал числа элементов, не включенных в выборку.
(11) .
Размещение образуется в два действия:
1) | образуется подмножество (выборка) размера r | |
2) | упорядочиваются элементы выборки |
В правом поле записано число способов выполнения каждого действия. По правилу умножения:
|
|
.
Пример. Сколько трехбуквенных слов можно составить из 26 различных карточек разрезной азбуки? Заметим, что в математике под словом понимается любая цепочка символов, необязательно осмысленная.
Нетрудно видеть, что образуемые слова суть размещения. В самом деле: эти слова являются упорядоченными выборками, а буквы (карточки) в слове не повторяются. Искомое число трехбуквенных слов равно:
26×25×24=15600.