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