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

abc, abd, acb, acd, adb, adc,

bac, bad, bca, bcd, bda, bdc,

cab, cad, cba, cbd, cda, bdc,

dab, dac, dba, dbc, dca, dcb.

Из составленной таблицы видно, что =24.

Число размещений из четырех элементов по три можно найти, не выписывая самих размещений. Первый элемент можно выбрать четырьмя способами, так как им может быть один из четырех элементов. Для каждого выбранного первого элемента можно тремя способами выбрать второй элемент из трех оставшихся. Наконец, для каждых первых двух элементов можно двумя способами выбрать из двух оставшихся третий элемент. В результате получаем, что =4·3·2=24.

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

Первый элемент можно выбрать n способами. Так как после этого остается n-1 элементов, то для каждого выбора первого элемента можно n-1 способами выбрать второй элемент. Далее, для каждого выбора первых двух элементов можно n-2 способами выбрать третий элемент (из n-2 оставшихся). Наконец, для каждого выбора первых k-1 элементов можно n – (k – 1) способами выбрать k-й элемент (из n – (k -1) оставшихся).

Значит, =

n

(

n

– 1)(

n

– 2)∙…∙(

n

– (

k

– 1))

Мы получили формулу для вычисления числа размещений из п элементов по k.

Например, число размещений из шестнадцати элементов по пять равно произведению пяти множителей, первый из которых – число 16, а каждый следующий на 1 меньше предыдущего, т.е. = 16·15·14·13·12=524160.

В пособии приводятся примеры применения формулы числа размещений.

Пример 1.

Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было четыре различных предмета?

Любое расписание на один день, составленное из 4 различных предметов, отличается от другого либо предметами, либо порядком следования предметов. Значит, в этом примере идет речь о размещениях из 8 элементов по 4. Имеем, = 8·7·6·5 = 1684.

Расписание можно составить 1680 способами.

Пример 2.

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

Если среди семи цифр нет нуля, то трехзначных чисел (без повторения), которые можно составить из этих цифр, равно числу размещений из 7 элементов по 3. однако среди данных цифр есть цифра 0, с которой не может начинаться трехзначное число. Поэтому из размещений из 7 элементов по 3 надо исключить те элементы, у которых первой цифрой является 0. их число равно числу размещений из 6 элементов по 2. значит, искомое число трехзначных чисел равно .

Из данных цифр можно составить 180 трехзначных чисел (без повторения цифр).

Упражнения

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

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

Сколькими способами могут занять первое, второе и третье места 8 участниц финального забега на дистанцию 100 м?

На станции 7 запасных путей. Сколькими способами можно расставить на них 4 поезда?

Сколькими способами можно изготовить трехцветный флаг с горизонтальными полосами, если имеется материал 7 различных цветов?

На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4×100 м на первом, втором, третьем и четвертом этапах?

Решение. В этом задании идет речь о размещениях из 12 элементов по 4. Таким образом, искомое число выбора спортсменок равно = 12·11·10·9 = 11880 способов.

Сколькими способами могут быть распределены первая, вторая и третья премии между 15 участниками конкурса?

Сколькими способами 6 студентов, сдающих экзамен, могут занять места в аудитории, в которой стоит 20 одноместных столов?

На странице альбома 6 свободных мест для фотографий. Сколькими способами можно вложить в свободные места:

а) 2 фотографии; б) 4 фотографии; в) 6 фотографий?

На плоскости отметили 5 точек. Их надо обозначить латинскими буквами. Сколькими способами это можно сделать (в латинском алфавите 26 букв)?

Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр: