Элементы комбинаторики (стр. 4 из 6)

7.

способами

8. а)

чисел

9. б) 39=19 683 чисел

3. Итог урока

Урок 8: Перестановки

Цели:

· познакомить учащихся с перестановками без повторений, перестановками с повторениями;

· закрепить новые формулы с помощью решения задач.

Оборудование: аншлаги с формулами

Ход урока

1. Сообщение темы и целей

2. Домашнее задание:

1) Сколькими способами можно разместить 12 человек за столом, на который поставлено 12 приборов?

2) Сколькими способами можно установить дежурство по одному человеку в день среди семи учащихся группы в течение семи дней?

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

4) Сколькими способами можно посадить за круглый стол пять мужчин и пять женщин так, чтобы никакие два лица одного пола не сидели рядом?

4. Работа по теме

4.1. Повторение

Решите задачу: на железнодорожной станции имеется nсемафоров. Сколько может быть дано различных сигналов при помощи этих семафоров, если каждый семафор имеет три состояния: горит либо зеленый, либо желтый, либо зеленый цвет.

Решение: имеем кортеж длины n(дано nсемафоров), каждый элемент которого можно выбрать тремя способами (каждый семафор имеет три состояния). Поэтому различных сигналов можно дать 3ⁿ.

- Дайте определение размещений без повторений

- Что такое факториал?

4.2. Понятие «перестановки без повторений»

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

- Выведем формулу.

Следовательно, число перестановок без повторений находится по формуле: Р_п=n!

Вычислите: Р₃; Р₅

Р₃=3!=6; Р₅=5!=120

4.3. Понятие «перестановки с повторениями»

Пусть дан кортеж длинны п, составленный из элементов множества Х={х₁, …, х_k}. Причем буква х₁ входит в этот кортеж п₁ раз, буква х_k= п_kраз. Тогда п=п₁ + … +п_k. Если переставлять в этом кортеже буквы, то будут получаться новые кортежи, имеющие тот же состав. Эти кортежи называются перестановками с повторениями из букв х₁,… , х_k, имеющими состав (п₁, … , п_k).

Число таких перестановок обозначается Р(п₁, … , п_k) и находится по формуле:

Упражнение. Вычислите: Р(2, 5, 3); Р(1, 2, 3, 4).

Решение. Р(2, 5, 3); п=2+5+3=10, п₁=2, п₂=5, п₃=3

5. Закрепление

Задача 1. Найдите число способов расстановки 8 ладьей на шахматной доске, при которых они не бьют друг друга.

Решение. Каждый искомый способ задается перестановкой 8 чисел1,2, … 8. Эти числа указывают номера горизонталей занятых полей на первой, второй, …, восьмых вертикалей. Значит, таких перестановок 8!. Таким образом, ладьи можно расставить 8!=40 320 способами.

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

Решение. Р₄=4!=24.

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

Решение. Р₅=5!=120

Задача 4. У Лены есть 8 разных красок. Она хочет написать ими слова «Новый Год». Сколькими способами она может это сделать, если каждая буква может быть раскрашена одним цветом и все 8 букв должны быть разные по цвету.

Решение. Присвоим каждой краске номер от 1 до 8. Тогда каждый искомый способ задается перестановкой 8 чисел 1,2, …, 8. Значит, таких перестановок 8!. Поэтому она может написать «Новый Год» 8!=40 320 способами.

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

Решение. 5!=120

Задача 6. Сколько различных кортежей получится, если переставлять буквы слова «математика»?

Решение. Это слово имеет состав: м – 2, а – 3, т – 2, е – 1, и – 1, к – 1, то есть (2, 3, 2, 1, 1, 1), поэтому получим Р(2,3,2,1,1,1)=

Задача 7. У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней она дает сыну по 1 фрукту. Сколькими способами это может быть сделано.

Решение. Р(2,3)=

Задача 8. Сколькими способами можно положить 28 различных открыток в 4 одинаковых конверта так, чтобы в каждом конверте было по 7 открыток?

Решение. Пометим конверты цифрами 1,2,3,4, тогда число различных раскладок равно Р(7,7,7,7)=

. Вычислять это значение не будем, так как оно очень большое.

Сотрем пометки. Теперь конверты можно произвольно переставлять друг с другом, не меняя результата расклада (теперь они не отличаются друг от друга). Так как число различных перестановок четырех конвертов равно Р₄=4!, то число различных раскладов уменьшается в Р₄=4! и поэтому оно равно

.

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

Решение. 3!∙3!=36 способами

6. Итог урока

- Что такое перестановки без повторений?

- По какой формуле находится число перестановок без повторений?

Урок 9. Сочетания

Цели:

· познакомить учащихся с сочетаниями без повторений и с повторениями;

· закрепить новые формулы с помощью решения задач.

Оборудование: аншлаги с формулами

Ход урока

1. Сообщение темы и целей

2. Домашнее задание на карточках

1) Из 20 учащихся кружка математики четверых необходимо отправить на олимпиаду. Сколькими способами можно составить команду?

Решение:

3) В вазе стоят 10 белых и 5 красных роз. Сколькими способами можно выбрать из вазы букет, состоящий из двух красных и одной белой розы?

Решение:

· = = 100.

3) Сколько существует различных треугольников, длины сторон которых принимают значения 5, 6, 7, 8, 9? Сколько из них равносторонних, равнобедренных и разносторонних?

4. Повторение

1) Назовите формулу размещений без повторений, размещений с повторениями, перестановок без повторений и перестановок с повторениями;

2) Назовите правила произведения и суммы.

5. Работа по новой теме

5.1. Понятие «сочетаний без повторений»

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

Введем определение:

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

Число сочетаний из п элементов по mобозначают

и читают «С из nпо m».

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

Число сочетаний без повторений равно:

Понятие «сочетаний с повторениями»

- Число сочетаний с повторениями из nэлементов по mвыражается через число сочетаний без повторений.

- Назовите формулу числа сочетаний без повторений.

Найдем число сочетаний с повторениями из четырех элементов А, Б, В, Г по три элемента:

ААА	АБВ	БББ	ГГГ
ААБ	АБГ	ББВ	ВВВ
ААВ	АВВ	ББГ	ВВГ
ААГ	АВГ	БВВ	ВГГ
АББ	АБГ	БВГ	ГГГ

Число сочетаний с повторениями обозначается символом

. В данном случае мы получили , тогда как число сочетаний без повторений из четырех элементов по 3 есть .

Формула числа сочетаний из mэлементов по nэлементов с повторениями имеет вид:

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

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