Размещения без повторений.
Рассмотрим множество А = {a1, a2, ...an}.Будем далее рассматривать размещения длины m элементов из множества А, не содержащие повторяющихся элементов, т.е. будем рассматривать такие соединения, которые отличаются друг от друга либо хотя бы одним элементом, либо порядком их расположения. При этом они не содержат повторяющихся элементов. Такие соединения называются размещениями без повторений и обозначаются .
При составлении таких соединений на первое место можно поставить любой из n элементов множества А, на второе – любой из n – 1 оставшихся элементов и, наконец. на m-е место – любой из n – (m – 1) оставшихся элементов. По правилу прямого произведения получаем, что общее число размещений без повторений из n по m равно = n(n – 1)(n – 2)...(n – m + 1) или
(*)
П р и м е р 2 . В хоккейном турнире участвуют 17 команд. Разыгрываются золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали?
Р е ш е н и е. 17 команд претендуют на три призовых места. Тогда указать команды, получившие золотую, серебряную и бронзовую медали, можно A 173 = 17∙16∙15 = 4080 способами.
- Дискретная математика.
- Множества.
- П римеры
- Или по другому
- Операции над множествами.
- Основные свойства операций над множествами.
- Алгебра высказываний.
- Логические операции над высказываниями.
- Отрицание.
- Конъюнкция.
- Эквиваленция
- Импликация.
- Формулы алгебры высказываний.
- Элементарные высказывания, символы логических переменных – формулы;
- Если f1 и f2 – формулы алгебры высказываний, то
- Других формул алгебры высказываний нет.
- Равносильность формул.
- Совершенная дизъюнктивная нормальная форма.
- Приведение формулы к сднф.
- Совершенная конъюнктивная нормальная форма.
- Приведение формулы к скнф.
- Полнота и замкнутость.
- Минимизация днф.
- Способы задания булевых функций.
- Табличный способ задания.
- Графический способ задания.
- Аналитический способ задания.
- Элементы теории графов.
- Матрицы графов.
- Некоторые общие понятия теории графов.
- Взвешенные графы и алгоритмы поиска кратчайшего пути.
- Задача о кратчайших путях.
- Элементы теории алгоритмов.
- Понятие автомата.
- Машина Тьюринга.
- Автомат Мили.
- Правило суммы.
- Правило прямого произведения.
- Размещения с повторениями.
- Размещения без повторений.
- Перестановки.
- Сочетания.
- Сочетания с повторениями.