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