Решение комбинаторных задач

Цель: научиться решать задачи с использованием понятий перестановок, сочетаний и размещений.

Место проведения: учебная аудитория, ОБОУ СПО «Курский электромеханический техникум».

Средства обучения:

- методические рекомендации к практической работе № 66.

Виды самостоятельной работы:

- нахождение числа размещений;

- вычисление числа перестановок;

- вычисление числа сочетаний.

Краткая теоретическая справка

Группы, составленные из каких-либо элементов, называются соединениями. Различают три основных вида соединений: размещения, перестановки и сочетания.

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

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

Число размещений без повторений из n элементов по m обозначается и вычисляется по формуле

.

Размещения с повторениями — комбинаторные соединения, составленные из n элементов по m. При этом каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать.

Формула для нахождения количества размещений с повторениями:

.

Перестановки без повторений — комбинаторные соединения, которые могут отличаться друг от друга лишь порядком входящих в них элементов.

Формула для нахождения количества перестановок без повторений:

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

Перестановки с повторениями — комбинаторные соединения, в которых среди образующих элементов имеются одинаковые. В таких соединениях участвуют несколько типов объектов, причём имеется некоторое количество объектов каждого типа. Поэтому в выборках встречаются одинаковые.

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

Формула для нахождения количества сочетаний без повторений:

Сочетания с повторениями — комбинаторные соединения из n элементов по m, составленные из этих элементов без учета порядка с возможностью многократного повторения предметов.

Формула для нахождения количества сочетаний с повторениями:

Правило суммы: если некоторый объект А можно выбрать m способами, а объект В – n способами, то выбор «либо А, либо В» можно осуществить m + n способами.

При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В.

Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k) способов выбора, где k —число совпадений.

Правило произведения: Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить mn способами.

При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.

Практические задания для аудиторной работы

1. Сколько различных двузначных чисел можно составить из цифр 1,2,3,4 при условии, что в каждом числе нет одинаковых цифр?

2. Сколько различных двузначных чисел можно составить из цифр 1,2,3,4?

3. Сколькими способами можно переставить 5 различных книг на книжной полке?

4. Человек забыл две последние цифры в шестизначном телефонном номере, помнит только, что они были неодинаковые и нечетные. Сколько таких телефонных номеров может быть?

Показать решение

5. Из трех инженеров и девяти экономистов должна быть составлена комиссия из 7 человек. Сколькими способами может быть составлена комиссия, если в неё должен входить хотя бы один инженер.

Практические задания для самостоятельной работы

Вариант 1

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

2. Сколько всего двузначных чисел?

3. На прямой взяли десять точек. Сколько всего получилось отрезков, концами которых являются эти точки?

4. Сколькими способами можно распределить 12 комнат под 12 учебных кабинетов?

5. Сколькими способами можно купить пиджак и брюки, если в магазине есть 7 видов пиджаков и 5 видов брюк?

Вариант 2

1. Сколько всевозможных двухзначных чисел можно записать из цифр 8, 7 и 5.

2. Сколько всего двузначных чисел, в записи которых цифры не повторяются?

3. В лотерее нужно зачеркнуть любые 8 чисел из 40. Сколькими способами это можно сделать?

Показать решение

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

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

Требования к отчёту:

1. После выполнения работы студент обязан продемонстрировать преподавателю выполненные задания.

2. Предоставить отчёт о выполненной работе, содержащий:

- порядковый номер и наименование практической работы;

- цель практической работы;

- ход выполнения работы;

- ответы на контрольные вопросы.

Контрольные вопросы

1. Что называют соединением? Какие виды соединений различают?

2. Что такое размещение без повторений и с повторениями?

3. Что называют перестановками без повторений и с повторениями?

4. Чем отличаются сочетания от размещений?

5. Дайте определение символа n!.

6. В чем заключаются правила суммы и произведения?

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