Элементы комбинаторики Размещения. Задача 1. Сколькими способами 9 человек могут встать в очередь в театральную кассу? Решение: P 9 = 9! = 9·8·7·6·5·4·3·2·1. - презентация

1 Элементы комбинаторики Размещения

2 Задача 1. Сколькими способами 9 человек могут встать в очередь в театральную кассу? Решение: P 9 = 9! = 9·8·7·6·5·4·3·2·1 = Ответ:

3 Задача 2. Сколько шестизначных чисел (без повторения цифр) можно составить из цифр: а) 1, 2, 5, 6, 7, 8; б) 0, 2, 5, 6, 7, 8? Решение: а) P 6 = 6! = 720; Ответ: а) 720; б) 1 способ (метод исключения лишних вариантов): P 6 – P 5 = 6! – 5! = = 600; 2 способ (правило произведения): 5·5·4·3·2·1 = 600. Ответ: б) 600.

4 Задача 3. Решите уравнение: а) n! = 7·(n-1)!; б) (k – 10)! = 77·(k – 11)! Решение: n! = 7·(n-1)! n·(n-1)! = 7·(n-1)! n = 7 Ответ: 7. Решение: (k – 10)! = 77·(k – 11)! (k – 10)·(k – 11)! = = 77·(k – 11)! K – 10 = 77 K = 87 Ответ: 87.

5 Задача 4. Сколькими способами можно расставить на полке 7 книг, из которых 3 книги – это книги одного автора, так, чтобы книги одного автора стояли рядом? Решение: Из 7 элементов 3 элемента можно «склеить» P 3 = 3! = 6 различными способами. Число различных перестановок из 5 элементов (4 элемента + «склейка») равно P 5 = 5! = 120. Общее число способов расставить 7 книг, из которых 3 должны стоять рядом, равно 6·120 = 720. Ответ: 720.

6 Задача. Пусть имеется 4 шара (красный, синий, зеленый и желтый) и 4 пустых ячейки. Сколько существует способов размещения шаров в ячейках? Решение: Число размещений 4 шаров в 4 ячейках равно числу перестановок из 4 элементов P 4 = 4! = 24. Ответ: 24.

7 Пусть имеется 4 шара (красный, синий, зеленый и желтый) и 3 пустых ячейки. Сколько существует способов размещения шаров в ячейках? Каждую упорядоченную тройку, которую можно составить из четырех элементов, называют размещением из четырех элементов по три.

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

9 Дерево возможных вариантов или граф-дерево. Число размещений из 4 шаров по 3 к с зж з тсж ж сс с к зж з кж ж кз з к тсж с кж ж кс ж к сс с кз з кс

10 Таблица размещений из четырех элементов по три. кcзкcзктсжкзскзжкжскжз скзскжсскстсжтсжктсжз зксскжзскзтсжзжкзжс жктсжкзжскжстсжзкжзс

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

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

13 Определение. Произведение k натуральных чисел, начинающееся с n, в котором каждый следующий множитель уменьшается на единицу, называется убывающим k-факториалом от n и обозначается (n) k.

14 Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета? Решение: Любое расписание на один день, составленное из 4 различных предметов, отличается от другого либо предметами, либо порядком следования предметов. Значит, речь идет о размещениях из 8 элементов по 4.

15 Задача 1. На странице альбома 6 свободных мест для фотографий. Сколькими способами можно вложить в свободные места: а) 2 фотографии; Ответ: 30. б) 4 фотографии; Ответ: 360. в) 6 фотографий? Ответ: 720.

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

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

18 Задача 3. Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами можно это сделать? Ответ: 870.

19 Задача 4. Сколькими способами могут занять первое, второе и третье места 8 участниц финального забега на дистанции 100 м? Ответ: 336.

20 Задача 5. На станции 7 запасных путей. Сколькими способами можно расставить на них 4 поезда? Ответ: 840.

21 Задача 6. Сколькими способами 6 учеников, сдающих экзамен, могут занять места в аудитории, в которой стоит 20 одноместных столов? Ответ:

22 Задача 7. На плоскости отметили 5 точек. Их надо обозначить латинскими буквами. Сколькими способами это можно сделать ( в латинском алфавите 26 букв)? Ответ:

23 Задача 8. Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр 1, 3, 5, 7, 9. Ответ: 120.

24 Домашнее задание. Задача 1. Сколькими способами организаторы конкурса могут определить, кто из 15 его участников будет выступать первым, вторым и третьим? Задача 2. Сколькими способами можно изготовить трехцветный флаг с горизонтальными полосами, если имеется материал 7 различных цветов? Составить и решить задачу на размещения из 25 элементов по 4.