Методика обучения решению комбинаторных задач (стр. 13 из 15)

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

Упражнения

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

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

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

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

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

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

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

= 12·11·10·9 = 11880 способов.

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

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

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

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

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

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

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

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

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

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

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

Решение. В этом задании идет речь о размещениях из 10 элементов по 7, т.е.

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

Так как из всех размещений надо исключить те, которые начинаются с цифры 0, то имеем:

= 10·9·8·7·6·5·4 – 9·8·7·6·5·4 = 604800 – 60480 = 544320.

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

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

4. Сочетания

Пусть имеется пять гвоздик разного цвета. Обозначим их буквами 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:

.

Следовательно, трех дежурных можно выбрать 455 способами.

Пример 2. Из вазы с фруктами, в которой лежит 9 яблок и 6 груш, надо выбрать 3 яблока и 2 груши. Сколькими способами можно сделать такой выбор?

Выбрать 3 яблока из 9 можно

способами, а выбрать 2 груши из 6 можно способами. Так как при каждом выборе яблок груши можно выбрать способами, то сделать выбор фруктов, о котором говорится в задаче, можно способами.

Значит, указанный выбор фруктов можно сделать 1260 способами.

Упражнения

68. В классе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?

69. В магазине «Филателия» продается 8 различных наборов марок, посвященных спортивной тематике. Сколькими способами можно выбрать из них 3 набора?

Решение. Искомое число способа выбора трех наборов равно

.

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

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

72. Сколькими способами можно выбрать 49 предметов из 50

73. Сколькими способами можно отобрать стартовую шестерку в волейбольном матче, если в команде заявлено 10 игроков?

74. Из лаборатории, в которой работают заведующий и 10 сотрудников, надо отправить 5 человек в командировку. Сколькими способами это можно сделать, если:

а) заведующий лабораторией должен ехать в командировку;

б) заведующий лабораторией должен остаться?

75. На полке стоит 12 книг: англо-русский словарь и 11 художественных произведений на английском языке. Сколькими способами читатель может выбрать 3 книги, если: