Элементы комбинаторики РАЗМЕЩЕНИЯ. Задача 1. Имеется 4 шара и 4 пустых ячейки в коробке. Сколько вариантов расположения шаров можно получить? Задача 2. - презентация

1 Элементы комбинаторики РАЗМЕЩЕНИЯ

2 Задача 1. Имеется 4 шара и 4 пустых ячейки в коробке. Сколько вариантов расположения шаров можно получить? Задача 2. Имеется 4 шара и 3 пустых ячейки в коробке. Какие варианты расположения можно получить? СРАВНИТЕ 2 ЗАДАЧИ:

3 Решение 1 задачи: Порядок расположения шаров задаётся условием 1,2,3,4. Это элементы множества, тогда число перестановок P 4 = n! = 4! = 24. – (искомое количество способов)

4 Отличие от предыдущей задачи: количество шаров превосходит количество ячеек. Т.е. невозможно применить теорему о количестве перестановок. Размещением из n элементов по k (k n) называется любое множество, состоящее из любых k элементов, взятых в определённом порядке из данных n элементов. Обозначение читают: «A из n по k»

5 Рассмотрим 1 из способов решения задачи 2. Присвоим шарам обозначения a, b, c, d. dbc abcabdacbacdadbadc bcabcdbadbdabdc cab bac cadcbdcbacdbcda dabdacdbadcbdca

6 * a bcd b acd c abd d abc Решим эту же задачу, используя дерево вариантов. Закончите построение дерева.

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

8 Решение 2 задачи: Размещение 4 элементов по 3. Количество множителей равно 3

9 Аналогично рассуждая, подсчитаем сколько можно составить размещений из n элементов по k, где kn. 1 элемент 2 элемент 3 элемент 4 элемент K-ый элемент n способов n-1 способов n-2 способов n-3 способов n – (k-1) способов из n элементов множества из n-2 элементов множества из n-3 элементов множества из n-(k-1) элементов множества из n-1 элементов множества

10 Правило вычисления размещений из n элементов по k элементов

11 Пример 1: В классе 27 учеников. К доске нужно вызвать двоих. Сколькими способами это можно сделать, если первый ученик должен решить задачу по геометрии, другой – по алгебре? Порядок выбора двух элементов множества из 27 элементов важен, поэтому: В данном случае k=2, потому количество множителей в формуле равно 2,значит:

12 Пример 2: В классе 27 учеников, из которых нужно выбрать троих. Первый ученик должен решить задачу, второй – сходить за мелом, третий – дежурить в столовую. Сколькими способами это можно сделать? Порядок во множестве из 27 элементов важен, поэтому: В данном случае k=3, потому количество множителей в формуле равно 3,значит:

13 Пример 3: Из 30 учащихся класса требуется выбрать старосту класса и заместителя старосты класса. Сколькими способами это можно сделать? В данном случае k=2, потому количество множителей в формуле равно 2,значит:

14 Вопрос дня: КАК различить: задача на перестановки или размещения? Количество рассматриваемых элементов множества совпадает с исходным количеством элементом меньше исходного количества элементов