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

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ, СТАТИСТИКИ И ТЕОРИИ ВЕРОЯТНОСТЕЙ

Тема 4.1. Элементы комбинаторики

План изучения темы:

1. Основные понятия комбинаторики. Задачи на подсчет числа размещений, перестановок, сочетаний. Решение задач на перебор вариантов.
2. Формула бинома Ньютона. Свойства биноминальных коэффициентов. Треугольник Паскаля

 

Прежде чем перейти к изучению нового материала, повторим то, что имеет к нему непосредственное отношение. Это уже известное вам понятие «факториал». Итак, кто помнит, что называют «n-факториалом»? Запишите формулу.

Факториа́л числа n — произведение всех натуральных чисел от 1 до n включительно:

Чему, к примеру, равны 2!, 3!, 4!, 5!, 6! ? А кто сможет показать вычисления на доске? А чему равен 1! ? 0! ? Какие значения в данном случае может принимать n?

Факториал определён только для целых неотрицательных чисел. По договоренности: .

 

Краткое изложение теоретических вопросов:

 

1. Комбинаторикойназывают область математики, которая изучает вопросы о числе различных комбинаций (удовлетворяющих тем или иным условиям), которые можно составить из данных элементов.

 

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

 

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

Различают три вида соединений: размещения, перестановки и сочетания.

Задачи, в которых производится подсчет возможных различных соединений, составленных из конечного числа элементов по некоторому правилу, называются комбинаторными, а раздел математики, занимающийся их решением, - комбинаторикой. Рассмотрим три основных вида соединений и формулы вычисления их количества. Для этого сначала рассмотрим 2 задачи, которые помогут нам сосредоточиться на сути новых понятий.

 

Задача 1.В некотором учреждении имеются две различные вакантные должности, на каждую из которых претендуют три сотрудника: A, B, C. Сколькими способами из этих трех кандидатов можно выбрать два лица на эти должности?

 

Задача 2.Для участия в соревнованиях требуется выбрать двоих спортсменов из трех кандидатов: A, B, C. Сколькими способами можно осуществить этот выбор?

Студентам предлагается два проблемных задания: 1) установить различие между этими двумя внешне схожими задачами и 2) предположить, в какой задаче результат будет больше, и почему. После этого предлагается решить эти задачи методом перебора всевозможных вариантов.

Решение задачи 1.AB, BA, BC, CB, AC, CA (всего шесть способов).

Решение задачи 2.AB, BC, AC (всего три способа).

Преподаватель обращает внимание студентов на то, что эти задачи оказались похожими только внешне, из-за того, что в обеих присутствуют два числа: m=3 – общее количество элементов и n=2 – количество выбранных элементов. Но в первой задаче составляются упорядоченные соединения, тогда как во второй задаче порядок следования элементов в соединении не имеет значения.

А если вместо чисел 3 и 2 будут например числа 8 и 3. Подойдет ли этот метод для решения этих задач? Поэтому существуют комбинаторные выражения (формулы) для этих соединений

Размещения

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

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

Пример 1.Решим задачу 1 с помощью этой формулы:

А теперь решим ту же задачу для случая m=8, n=3:

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

Перестановкой из n элементовназывают размещение из n элементов по n.

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

Задача. Сколькими способами можно расположить в столбик три детали конструктора, различающиеся по цвету?

способами.

Сочетания

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

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

Пример 2.Решим задачу 2 с помощью этой формулы:

А теперь решим ту же задачу для случая m=8, n=3:

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

второй. Мы рассмотрели теоретические основы комбинаторики.

Теперь перейдем к этапу закрепления новых знаний при решении задач.

 

Закрепление материала

ЗАДАЧА 1

 

ЗАДАЧА 2

Определить, важен или нет порядок в следующих выборках, правильный ответ подчеркнуть:

а) судья хоккейного матча и его помощник; да, нет.

б) три ноты в аккорде; да, нет.

в) «Шесть человек останутся убирать класс!» да, нет.

г) две серии для просмотра из многосерийного фильма. да, нет.

 

Закрепление материала

ЗАДАЧА 1

 

 

ЗАДАЧА 2

Определить, важен или нет порядок в следующих выборках, правильный ответ подчеркнуть:

а) судья хоккейного матча и его помощник; да, нет.

б) три ноты в аккорде; да, нет.

в) «Шесть человек останутся убирать класс!» да, нет.

г) две серии для просмотра из многосерийного фильма. да, нет.

 

 

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

При решении комбинаторных задач важно научиться различать виды соединений. Чтобы отличать задачи на подсчёт числа размещений от задач на подсчёт числа сочетаний, определим, важен или нет порядок в следующих выборках:

а) судья хоккейного матча и его помощник;

б) три ноты в аккорде;

в) «Шесть человек останутся убирать класс!»

г) две серии для просмотра из многосерийного фильма.