Определение 8: Конечные упорядоченные множества называются размещениями.
Определение 8: Конечные упорядоченные множества называются размещениями. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Теорема 3: Количество Всех Размещений Из ...
Теорема 3: Количество всех размещений из элементов по элементов без повторений вычисляется по формуле:
. (2)
Доказательство. Пусть имеется произвольное множество , состоящее из элементов. Необходимо выбрать из этого множества различных элементов. Причем, важен порядок выбора.
Выбор элементов осуществляется поэтапно. Первый элемент расстановки можно выбрать различными способами. Тогда из оставшихся элементов множества второй элемент расстановки выбирается способом. Для выбора третьего элемента возможно способа и т.д. Тогда для выбора - го элемента имеем способ. Следовательно, согласно правилу умножения, количество таких расстановок будет равно:
.
По определению, такие расстановки являются размещениями. Что и требовалось доказать.
Пример 3: Собрание из 25 человек выбирает президиум из 3 человек: 1) председатель, 2) заместитель, 3) секретарь. Сколько возможно вариантов выбора президиума?
Решение. Выбирая трех человек из 25, замечаем, что важен порядок выбора, поэтому количество президиумов будет равно:
.
Замечание: Число размещений без повторений можно также находить по формуле:
. (3)
Если в знаменателе дроби из формулы (3) , то принято считать .
Замечание: Формула (3) отличается компактностью, но при решении задач удобнее использовать формулу (2). Дробь, стоящая в правой части формулы (3), может быть сокращена до целого числа. Это число равно числу из правой части формулы (2).
Пример 4: Сколько можно составить двухбуквенных слов (буквы не повторяются) из 33 букв русского алфавита?
Решение. В данном случае мы имеем дело не со словами в лингвистическом понимании, а с буквенными комбинациями произвольного состава.
Тогда количество различных комбинаций из 2 букв, выбранных из 33 букв алфавита, будет равно:
.
В данном случае важен порядок букв. Если поменять 2 буквы в слове, то получим новое слово.
Замечание: Перестановка без повторений – это частный случай размещений без повторений при . Можно сказать, что перестановка из элементов – это размещение из элементов по элементов:
В некоторых задачах по комбинаторике не имеет значения порядок расположения объектов в той или иной совокупности. Важно лишь то, какие именно элементы ее составляют. В таких ситуациях мы имеем дело с сочетаниями.
Сочетания без повторений.
Определение 9:Сочетаниябез повторений из элементов некоторого множества по элементов () – это расстановки, отличающиеся друг от друга составом, но не порядком элементов. Обозначают: (от французского слова combinaison – сочетание).
В данном случае в расстановках важен состав, а не порядок элементов в подмножестве. Если две расстановки отличаются только порядком следования элементов, то с точки зрения сочетаний они не различимы. Элементы в этих расстановках не повторяются.
С точки зрения теории множеств определение сочетаний можно сформулировать иначе.
Представление бинарных отношений графами.
Понятие графа используется в математике для наглядного представления бинарных отношений, заданных на конечных множествах.
Граф представляет собой конечный набор точек плоскости (
И порядка. Фактор-множество.
В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар
Булевы алгебры.
Определение 1: Пусть - отношение порядка на множестве
Трансфинитная индукция.
Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами
Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают.
2) Обозначим через множес
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм
Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём следующие обозначен
Правила комбинаторики.
Начнем с основных принципов комбинаторики, т.е. с правил.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило слож
Свойства сочетаний.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след
Комбинаторика с повторениями.
Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по комбинаторике необходимо определить
Упражнения для самостоятельной работы.
1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов