Перестановки - Элементы комбинаторики - Элементы комбинаторики и теории вероятностей

Цель: рассмотреть простейший вид соединений - перестановки.

Ход урока

I. Сообщение темы и цели урока

II. Повторение и закрепление пройденного материала

1. Ответы на вопросы по домашнему заданию (разбор нерешенных задач).

2. Контроль усвоения материала (самостоятельная работа).

Вариант 1

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

2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 5, 6, 7?

Вариант 2

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

2. Сколько трехзначных нечетных чисел можно составить из цифр 0, 2, 3, 4, 5, 6, 7, 9?

III. Изучение нового материала

Введем некоторые необходимые понятия.

Соединением из и элементов по к назовем выборку k элементов из различных элементов (k ≤ n).

Пример 1

Пусть даны три различных элемента (n = 3): a, b и с. Перечислим соединения из трех элементов по одному (k = 1): а, b, с:

- соединения из трех элементов по два (k = 2): ab, bа, ас, са, bс, cb;

- соединения из трех элементов по три (k = 3): abc, асb, bас, bса, cab, cba.

В зависимости от того, имеет ли значение порядок элементов или нет, а также от того, входят ли в соединение все n элементов или только k (при условии, что k < n), различают три вида соединений: перестановки, размещения, сочетания.

Комбинаторика изучает число таких соединений (но не сами соединения).

Сначала рассмотрим простейший вид соединений - перестановку. Соединения, каждое из которых содержит n различных элементов, взятых в определенном порядке, называются перестановками из n элементов. Другими словами, имеется n позиций (мест), которые надо заполнить n различными элементами:

Пример 2

Рассмотрим перестановки из трех элементов: а, b, с.

Необходимо расположить на три позиции три элемента.

Если на первую позицию поставить элемент а, то возможны перестановки: аbс, асb.

Если на первую позицию поставить элемент b, то возможны перестановки: bас, bса.

Если на первую позицию поставить элемент с, то возможны перестановки: cab, cba,

Видно, что число перестановок из трех элементов равно 6. Вообще, число перестановок из n элементов обозначают символом Рn (читается: Р из n). В данном примере Р3 = 6.

Выведем формулу числа Рn перестановок из n элементов. Используем комбинаторное правило умножения. На первую позицию можно поместить любой из и элементов, на вторую позицию - любой из оставшихся (n - 1) элементов, на третью позицию - любой из оставшихся (n - 2) элементов и т. д.

В результат получим: Рn = n(n - 1)(n - 2) · ... · 3 · 2 · 1.

Расположим множители в порядке возрастания. Имеем: Рn = 1 · 2 · 3 · ... · (n - 2)(n - 1)n.

Для произведения первых n натуральных чисел используют символ n! (читается: n факториал), т. е. n! = 1 · 2 · 3 · ... · (n - 2)(n - 1)n.

При этом: 1! = 1 (и 0! = 1). Тогда число всевозможных перестановок из и элементов вычисляется по формуле Рn = n!

Пример 3

Вычислим:

а) Р3 = 3! = 1 · 2 · 3 = 6 (см. пример 2);

б)

в)

Пример 4

Решим уравнение

Упростим левую часть уравнения, пользуясь определением факториала: или или или 0 = n2 – 5n + 6.

Корни этого квадратного уравнения n = 2 и n = 3 действительно являются натуральными числами и решениями данного уравнения.

Пример 5

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

Число таких способов равно числу перестановок из 7 элементов, т. е. Р7 = 7! = 1 · 2 · 3 · ... · 7 = 5040.

Пример 6

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

Так как справочники должны стоять рядом, то будем рассматривать их как одну книгу. Тогда на полке надо расставить 10 – 3 + 1 = 8 книг. Это можно сделать Р8 способами. Для каждой из полученных комбинаций можно сделать Р3 перестановок справочников. Поэтому число способов расположения книг на полке равно произведению: P8 · Р3 = 8! · 3! = 40 320 · 6 = 241 920.

Пример 7

Сколько различных пятизначных чисел, в которых цифры не повторяются, можно составить из цифр 0, 1, 3, 6,9?

Из пяти цифр можно получить Р$ перестановок. Из них надо исключить те перестановки, которые начинаются с нуля (т.к. первая цифра в числе не может быть нулем). Число таких перестановок Р4.

Тогда получаем: Р5 - Р4 = 5! - 4! = 4! · 5 - 4! = 4! · (5 - 1) = 4! · 4 = 24 · 4 = 96 пятизначных чисел.

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

1. Соединение из n элементов по k.

2. Перечислите три вида соединений.

3. Дайте определение перестановок из n элементов.

4. Понятие факториала (n!).

5. Число перестановок из n элементов.

V. Задание на уроке

№ 732; 734; 737 (а); 738 (б); 739; 740 (а); 741 (а, в); 742; 745; 746 (а, г); 747 (б, в); 748 (а, г); 750 (б).

VI. Задание на дом

№ 733; 735; 736; 737 (б); 738 (а); 740 (б); 741 (б); 743; 744; 746 (б, в); 747 (а, г); 748 (б, д); 750 (а).

VII. Подведение итогов урока