- •В. Ф. Пуркина, е. В. Кайгородов
- •Оглавление
- •§1. Элементы математической логики
- •Высказывания
- •Упражнения
- •Равносильность формул. Виды формул
- •Упражнения
- •Предикаты и кванторы Предикаты
- •Упражнения
- •Логические законы, правила вывода. Метод математической индукции Законы логики
- •Упражнения
- •Теоремы стандартного вида. Необходимые и достаточные условия
- •Вопросы для самоконтроля
- •Упражнения
- •Самостоятельная работа по теме «Элементы математической логики»
- •§2. Множества и элементы комбинаторики
- •Множества
- •Упражнения
- •Элементы комбинаторики. Перестановки, размещения, сочетания
- •Правило произведения
- •Перестановки, размещения и сочетания
- •Упражнения
- •Бином Ньютона. Треугольник Паскаля Свойства сочетаний
- •Треугольник Паскаля
- •Формула бинома Ньютона
- •Упражнения
- •Самостоятельная работа по теме «Множества и элементы комбинаторики»
- •Соответствия и отношения
- •Операции над соответствиями
- •Упражнения
- •Свойства и типы соответствий Виды соответствий
- •Упражнения
- •Бинарные отношения и их свойства Отношения
- •Упражнения
- •Отношения эквивалентности и порядка. Фактор-множество
- •Самостоятельная работа по теме «Соответствия и отношения»
- •§4. Операции на множествах и их свойства
- •Упражнения
- •Исследование свойств бинарных операций на числовых множествах
- •Упражнения
- •Зачетная контрольная работа
- •6. Глоссарий
- •7. Основная и дополнительная литература
- •7.1. Основная литература
- •Дополнительная литература
- •Элементарная математика
Упражнения
1. Доказать:
а) А \ (ВС) = (А \ В) \ С;
б) А \ (В \ С) = (А \ В)(АС);
в) (АВ) \ С = (А \ С) (В \ С);
г) (АВ)(А \В) = А;
е) А\B=А\(ВА);
ж) А(В \ С) = (АВ) \ С;
и) (А \ В) \ С = (А \ С) \ (В \С);
к) (А\В) = А(ВА);
л) (АВС)=А (ВС).
2. Решить систему:
,
Элементы комбинаторики. Перестановки, размещения, сочетания
Пусть даны два произвольных множества A и B.
О п р е д е л е н и е 1. Декартовым (прямым) произведением множеств А и В называют множество, состоящее из всех упорядоченных пар вида , где и .
Символически это множество записывают так:
,
П р и м е р 1: Если А={1, 2, 3}, а В={0, 4}, то
;
.
Видим, что в общем случае .
П р и м е р 2: .
П р и м е р 3: RR = R2 ― плоскость (двумерное пространство); RRR = R3 ― трехмерное пространство.
З а м е ч а н и е: Если , а , то .
Прямое произведение можно определить и для нескольких множеств :
О п р е д е л е н и е 2.
.
Аналогичным образом можно ввести понятие декартовой степени множества А:
О п р е д е л е н и е 3.
.
Правило произведения
В математике важную роль играют комбинаторные задачи, связанные с подсчетом числа элементов различных конечных множеств, перебором конечного числа вариантов и т.п.
Одним из основных правил, которые применяются при решении таких задач, является правило произведения.
Пусть элемент можно выбрать способами, а элемент ― способами, тогда пару элементов можно выбрать способами. Это правило следует из определения декартова произведения двух множеств.
З а м е ч а н и е: Это правило распространяется и на множеств.
Приведем примеры решения комбинаторных задач с помощью правила произведения.
З а д а ч а 1. Пусть дан упорядоченный набор длины , т.е. , каждый элемент которого может принимать одно из двух значений (например, 0 или 1). Требуется узнать, сколько будет таких наборов (их называют двоичными). Для решения построим клетку с ячейками, каждую из которых можно заполнить двумя способами (например, 0 или 1; или «и» и «л» и т.п.):
2 способа |
2 способа |
2 способа |
… |
2 способа |
1 |
2 |
3 |
… |
n |
Следовательно, число двоичных наборов длины n равно . В частности, таблица истинности для логической формулы с n высказывательными переменными имеет строк, так как каждая строка таблицы представляет собой двоичный набор длины n.
З а д а ч а 2. Пусть дано множество . Нужно определить число всех его подмножеств . Пусть . Тогда этому подмножеству можно поставить в соответствие двоичный набор длины n, в котором на i-ом месте стоит 1, если , либо 0, если . Тогда .
Перестановки, размещения и сочетания
Перестановки. Одна из наиболее распространенных комбинаторных задач такова: сколькими способами можно переставить элементы некоторого конечного множества? Например: сколько 9-значных чисел с различными цифрами можно составить из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9?
При каждой перестановке n-элементного множества образуется упорядоченный набор длины n, все элементы которого различны. Число всех возможных перестановок в данном множестве совпадает с числом всех таких наборов.
О п р е д е л е н и е 4: Перестановкой из n элементов называется упорядоченный набор длины n с различными элементами, взятыми из некоторого n-элементного множества.
Число перестановок из n элементов обозначают Рn. Выведем формулу для вычисления Рn.
Пусть некоторое множество М состоит из n элементов. Рассмотрим произвольную перестановку элементов этого множества, то есть упорядоченный набор (), где аi∈ М. Элемент а1 в этом наборе можно выбрать n различными способами (взять любой элемент из множества M); элемент а2 выбирается n-1 способами (так как один элемент уже использован для а1, а элементы в перестановке не повторяются); а3 выбирается n-2 способами («заняты» два элемента) и т.д. Последний элемент аn можно выбрать только одним способом. По правилу произведения, будет всего указанных наборов.
Произведение , где n ― натуральное число, большее 1, называется n-факториалом и обозначается n! Дополнительно полагают: 1!=0!=1. Таким образом, .
Получена формула числа перестановок из n элементов. Применяя эту формулу, можно, в частности, получить, что из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 можно составить 9!, то есть 362880 9-значных чисел с различными цифрами.
Размещения. Другой важный тип комбинаторной задачи можно продемонстрировать на следующем примере: сколькими способами из 10 учебных предметов можно составить расписание занятий на один день, включив в него 4 различных предмета? Очевидно, что один вариант расписания может отличаться от другого как предметами, так и порядком их следования. Поэтому данную задачу можно сформулировать так: сколько существует упорядоченных наборов длины 4 с различными элементами, взятыми из 10-элементного множества? Число всех таких наборов называется числом размещений из 10 элементов по 4.
О п р е д е л е н и е 5: Размещением из n элементов по m (m≤n) называется упорядоченный набор длины m различными элементами, взятыми из некоторого n-элементного множества.
Еще раз напомним, что упорядоченные наборы с одними и теми же элементами, но разным порядком их следования считаются различными.
Обозначим число размещений из n элементов по n через и выведем формулу для вычисления .
Рассмотрим n-элементное множество M и произвольный упорядоченный набор (), где ai∈M для всех i, i = =1,2,...,m. Элемент а1 выбирается n различными способами; a2 выбирается n-1 способами и т.д. Последний элемент аm можно выбрать (n - (m - 1)), то есть (n - m + 1) способами. По правилу произведения, имеется всего указанных наборов.
Искомая формула имеет вид:
(1)
Заметим, что произведение в правой части состоит в точности из m множителей. Это облегчает применение формулы.
Вернемся к задаче о расписании. Число всех вариантов расписания можно посчитать по формуле (1): .
Имеет место другая формула для :
Для ее вывода достаточно преобразовать правую часть формулы (1).
Сочетания. Рассмотрим теперь такую задачу: сколькими способами можно из 10 учебных предметов выбрать 4 для составления расписания на день? Заметим, что в этой задаче, в отличие от задачи предыдущего пункта, не требуется составлять расписание, то есть упорядочивать предметы. Нужно узнать, сколькими способами из множества, состоящего из 10 элементов, можно выбрать 4-элементное подмножество (а не упорядоченный набор). Число таких подмножеств называют числом сочетаний из 10 элементов по 4.
О п р е д е л е н и е 6: Сочетанием из n элементов по m (m≤n) называется m-элементное подмножество n-элементного множества.
Подчеркнем, что в данном случае не различаются подмножества, состоящие из одних и тех же элементов, в каком бы порядке эти элементы не перечислялись.
Число сочетаний из n элементов по m обозначают . Выведем формулу для нахождения этого числа.
Пусть дано множество из n элементов. Возьмем произвольное m-элементное подмножество этого множества и составим из него все возможные упорядоченные наборы. Их будет m! Проделав такое действие с каждым подмножеством, получим множество всех упорядоченных наборов длины m, то есть всех размещений из n элементов по m. Их число .
Таким образом, . Отсюда: .
Иногда последнюю формулу записывают по-другому:
.
Применив полученную формулу, найдем :
.
Число 210 дает ответ задачи, поставленной в начале этого пункта.