Презентация "Элементы комбинаторики - размещения"

Элементы комбинаторики -

• РАЗМЕЩЕНИЯ

Задача 1. Имеется 4 шара и 4 пустых ячейки в коробке. Сколько вариантов расположения шаров можно получить?

• Задача 2. Имеется 4 шара и 3 пустых
• ячейки в коробке.
• Какие варианты расположения можно
• получить?

• СРАВНИТЕ 2 ЗАДАЧИ:

Решение 1 задачи:

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

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

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

• Обозначение

• читают: «A из n по k»

Рассмотрим 1 из способов решения задачи 2.

• Присвоим шарам обозначения a, b, c, d.

d

b

c

a

b

c

a

b

d

a

c

b

a

c

d

a

d

b

a

d

c

b

c

a

b

c

d

b

a

d

b

d

a

b

d

c

c

a

b

b

a

c

c

a

d

c

b

d

c

b

a

c

d

b

c

d

a

d

a

b

d

a

c

d

b

a

d

c

b

d

c

a

• *

• a

• b

• c

• b

• c

• d

• a

• c

• d

• a

• b

• d

• d

• a

• b

• c

• Решим эту же задачу, используя дерево вариантов.
• Закончите построение дерева.

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

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

Решение 2 задачи:

• Размещение 4 элементов по 3.
• Количество множителей равно 3

Аналогично рассуждая, подсчитаем

• Аналогично рассуждая, подсчитаем
• сколько можно составить размещений из n
• элементов по k , где k≤n.

• 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 элементов множества

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

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

• В данном случае k=2, потому количество множителей
• в формуле равно 2,значит:

Пример 2:

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

• В данном случае k=3, потому количество множителей
• в формуле равно 3,значит:

Пример 3:

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

• В данном случае k=2, потому количество множителей
• в формуле равно 2,значит:

• Вопрос дня: КАК различить: задача на перестановки или
• размещения?

• Количество рассматриваемых элементов множества

• совпадает с исходным
• количеством элементом

• меньше исходного
• количества элементов