Методы решения комбинаторных задач (электив 10 класс)

МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ

1. Непосредственные подсчеты

Задача 1. Андрей, Борис, Виктор и Григорий после возвращения из спортивного лагеря подарили на память друг другу свои фотографии. Причем каждый мальчик подарил каждому по одной фотографии. Сколько всего фотографий было подарено?

Решение. Процесс обмена фотографиями показан с помощью стрелок на ребрах полного графа с вершинами А, Б, В и Г. Количество подаренных фотографий равно количеству стрелок, то есть 12.

Ответ: 12.

2. Правило умножения

Задача 2. В меню столовой указано 5 закусок, 3 первых блюда, 4 вторых и 3 десерта. Каким числом способов можно заказать обед из четырех блюд?

Решение. Закуску выбираем 5 способами, первое блюдо – 3 способами, второе блюдо – 4 способами, десерт – 3 способами. Всего 5•3•4•3 =180 способов заказать обед.

Ответ:180.

3. Правило сложения

Задача 3. Из города А в город В ведет 5 дорог, из города А в город С ведет 4 дороги; из В в D – 3 дороги; из С в D – 6 дорог. В и С маршрутами не соединены. Сколько маршрутов можно провести между городами А и D?

Решение. Из города А в город D через город В ведет 5•3 =15 дорог (по правилу умножения), из города А в город D через город С ведет 4•6 = 24 дороги. Общее количество маршрутов между городами А и D по правилу сложения равно 15+ 24 = 39.

Ответ: 39.

4. Перестановки

Задача 4. Сколькими способами можно разместить на полке 4 книги?

Решение. Число способов разместить на полке 4 книги равно числу перестановок из четырех элементов: 4!= 24.

Ответ: 24.

5. Размещения

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

Решение. Из десяти цифр можно образовать = 604800 семизначных телефонных номеров, в каждом из которых ни одна цифра не повторяется.

Ответ: 604800.

1.6. Сочетания

Задача 6. В розыгрыше первенства по футболу принимают участие 16 команд, при этом любые две команды играют между собой только один матч. Сколько всего календарных игр?

Решение. Число календарных игр равно =120.

Ответ: 120.

2

Задачи для самостоятельного решения.

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

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