Сборник основных правил комбинаторики и упражнений для их применения

а) 1, 3, 5, 7, 9; б) 0, 2, 4, 6, 8?

Из трехзначных чисел, записанных с помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 (без повторения цифр), сколько таких, в которых:

а) не встречаются цифры 6 и 7;

б) цифра 8 является последней?

Сколько существует семизначных телефонных номеров, в каждом из которых все цифры различные и первая цифра отлична от нуля?

Решение. В этом задании идет речь о размещениях из 10 элементов по 7, т.е. . Но первая цифра номера должна отличаться от нуля, т.е. размещение из 9 элементов по 6.

Так как из всех размещений надо исключить те, которые начинаются с цифры 0, то имеем: = 10·9·8·7·6·5·4 – 9·8·7·6·5·4 = 604800 – 60480 = 544320.

Сколько различных трехзначных чисел (без повторения цифр) можно составить из цифр 1, 2, 3, 4, 5, таких, которые являются:

а) четными; б) кратными 5?

Сочетания

Пусть имеется пять гвоздик разного цвета. Обозначим их буквами a, b, c, d, е. требуется составить букет из трех гвоздик. Выясним, какие букеты могут быть составлены.

Если в букет входит гвоздика а, то можно составить такие букеты:

abc, abd, abe, acd, ace, ade

Если в букет не входит гвоздика а, но входит гвоздика b, то можно получить такие букеты:

bcd, bce, bde.

Наконец, если в букет не входит ни гвоздика а, ни гвоздика b, то возможен только один вариант составления букета: cde.

Мы указали все возможные способы составления букетов, в которых по-разному сочетаются три гвоздики из данных пяти. Говорят, что мы составили все возможные сочетания из пяти элементов по три.

Сочетанием из п элементов по k (0<k<n) называется любое множество, составленное из k элементов, выбранных из данных п элементов.

Число сочетаний из п элементов по k обозначают (читают «С из n по k»).

В отличие от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания из n элементов по k отличаются друг от друга хотя бы одним элементом.

В рассмотренном примере, составив все сочетания из 5 элементов по 3, мы нашли, что

Выведем формулу числа сочетаний из п элементов по k, где k≤n. Для этого сначала выясним, как выражается через и .

Мы нашли, что из пяти элементов a, b, c, d, e можно составить следующие сочетания по трем элементам:

abc, abd, abe, acd, ace, ade, bed, bec, bde, cde.

В каждом сочетании выполним все перестановки. Число таких перестановок равно Р3. В результате получим все возможные комбинации из 5 элементов по 5, которые отличаются либо самими элементами, либо порядком элементов, т.е. все размещения из 5 элементов по 3. всего мы получим размещений.

Значит, . Отсюда .

Аналогично будем рассуждать и в общем случае. Допустим, сто имеется множество, содержащее n элементов, и из его элементов составлены все возможные сочетания по k элементов. Число таких сочетаний равно . В каждом сочетании можно выполнить Pk перестановок. В результате мы получим все размещения, которые можно составить из n элементов по k. Их число равно .

Значит, . Отсюда, .

Мы получили формулу: .

Формулу числа сочетаний можно записать в другом виде. Умножим числитель и знаменатель дроби на (n – k)!, где n ¹ k. Получим:

Очевидно, что в числителе дроби записано произведение всех натуральных чисел от n до 1, взятых в порядке убывания, т.е. числитель дроби равен п!.

Получаем формулу: .

Заметим, что эту формулу можно использовать и в случае, когда n=k, если принять по определению, что 0!=1.

Пример 1.

Из 15 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор?

Каждый выбор отличается от другого хотя бы одним дежурным. Значит, здесь речь идет о сочетаниях из 15 элементов по 3:

.