Файл: 1. Общие правила комбинаторики правила суммы, произведения и биекции. Булеан конечного множества. Примеры.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.10.2023
Просмотров: 69
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
1. Общие правила комбинаторики: правила суммы, произведения и биекции. Булеан конечного множества. Примеры.
Правило суммы
Это правило позволяет найти число элементов в объединении двух конечных множеств и : . (1)
Если множества и не пересекаются ( ), то .
Идея его применения состоит в том, что, если в исходной задаче прямой подсчет затруднителен, то нужно все изучаемые комбинации разбить на несколько классов, причем каждая комбинация должна входить только в один класс. В этом случае общее число комбинаций равно сумме чисел комбинаций во всех классах. Иногда правило суммы формулируют следующим образом:
если объект можно выбрать способами, а объект – способами, то выбор «либо , либо » можно осуществить способами.
Правило произведения
Это правило позволяет подсчитать число кортежей, которые можно составить из элементов данных конечных множеств. Для двух множеств и (3)
Из равенства (3) следует, что число упорядоченных пар, которые можно составить из элементов множеств и равно произведению числа элементов в этих множествах.
Это правило можно сформулировать иначе:
если объект можно выбрать способами и после каждого из таких выборов другой объект можно выбрать способами, то выбор « и » можно осуществить способами.
По индукции правило умножения можно распространить на любое число сомножителей в декартовом произведении: . (4)
Наиболее часто последнее равенство применяется, когда : .
В этом случае множество называют алфавитом, его элементы – буквами, а элементы декартова произведения – словами в алфавите .
Правило биекции
Это правило, которое называется также принципом взаимно однозначного соответствия, формулируется следующим образом:
если между множествами и можно установить взаимно однозначное соответствие (биекцию), то .
В качестве примера применения этого принципа найдем мощность множества всех подмножеств данного множества . Такое множество называют булеаном множества и обозначают символом .
Пусть – -множество. Так как мощность множества не зависит от природы его элементов, то можно принять .
Поставим в соответствие произвольному подмножеству двоичное слово по следующему правилу:
Это соответствие взаимно однозначное. Отсюда следует, что число всех подмножеств -множества равно числу двоичных слов длины , то есть .
2. Метод включений и исключений. Пример.
Поставим задачу подсчитать количество элементов в объединении конечных множеств , которые могут иметь непустые пересечения между собой, т. е. это объединение в общем случае не является разбиением.
Для двух множеств имеем формулу (1). Обозначим и применим эту формулу для трех множеств, используя дистрибутивность операций объединения и пересечения множеств:
(6)
В результате по индукции получаем формулу включений и исключений:
(7)
Название этой формулы подчеркивает использование последовательных включений и исключений элементов подмножеств.
3. Понятие выборки.Размещения и формулы для их подсчета с повторениями и без повторений элементов. Примеры.
Понятие выборки
Набор элементов из множества называется выборкой объема из элементов или -выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней задан. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов не является существенным, то выборка называется неупорядоченной. В выборках могут допускаться или не допускаться повторения элементов. В зависимости от способа формирования все выборки в комбинаторике классифицируют как размещения, перестановки и сочетания с повторениями и без повторений элементов.
Размещения
-размещением с повторениями из элементов называется упорядоченная -выборка, в которой элементы могут повторяться. Число всех таких выборок, которые отличаются друг от друга составом элементов или их порядком, равно числу векторов в декартовом произведении . Это число обозначают (от французского слова arrangement – размещение). По правилу произведения получаем .
-размещением без повторений из элементов называется упорядоченная -выборка, в которой элементы не повторяются. Число всех упорядоченных -множеств с различными элементами, которые можно составить из элементов -множества , обозначают .
Для вычисления необходимо сделать выборов. 1-й элемент можно выбрать способами, 2-й – ( ) способами и т. д. Последний -й элемент можно выбрать способами. По правилу произведения . (2)
Здесь – « -факториал» (0!=1!=1).
4. Понятие выборки.Перестановки и формулы для их подсчета с повторениями и без повторений элементов. Примеры.
Перестановками без повторений называют различные упорядоченные -множества, которые состоят из одних и тех же элементов, а отличаются друг от друга лишь порядком. Число таких перестановок обозначают
Формулу для получаем из выражения при : .
Пример. Сколькими способами можно посадить на скамейку 9 человек? Ответ: =9!=362880.
К перестановкам с повторениями приводит следующая задача.
Имеется -множество , состоящее из различных элементов ( ). Сколько перестановок можно сделать из элементов первого типа, элементов второго типа,…, элементов -го типа?
Перестановки элементов каждого типа можно делать независимо друг от друга. Поэтому по правилу произведения элементы множества можно переставлять друг с другом способами так, что перестановки не изменятся. Тогда число различных перестановок с повторениями буде равно
, (4)
где .
Пример 4. Сколько перестановок можно сделать из букв слова «Миссисипи»?
В данном случае , («М»), («и»), («с»), («п»). По формуле (4)
.
5. Понятие выборки. Сочетания и формулы для их подсчета с повторениями и без повторений элементов. Примеры.
. К сочетаниям без повторений приводит следующая задача комбинаторики.
Сколько -элементных подмножеств с различными элементами можно составить из элементов -множества ?
Такие подмножества называют сочетаниями без повторений из элементов по или короче -сочетаниями, а их число обозначают (от французского слова combinaison – сочетание). Другими словами, сочетаниями без повторений называется неупорядоченная -выборка, в которой элементы не повторяются.
Формулу для числа сочетаний легко получить из формулы (2) для числа размещений. Выберем какое-нибудь -элементное подмножество . Его можно упорядочить способами, а число таких подмножеств есть . Тогда справедлива формула , (5)
откуда . (6)
Пример 5. Сколько всего партий играется в шахматном турнире с участниками?
Ответ: , так как каждая партия однозначно определяется двумя ее участниками.
Пусть множество состоит из элементов различных типов: . Множество , составленное из , в
котором элементы могут повторяться, называется мультимножеством. Для задания мультимножества надо указать число вхождений в него каждого элемента:
,где – мощность мультимножества.
Число мультимножеств мощности , составленных из элементов -множества , называют сочетаниями с повторениями и обозначают . Другими словами, сочетаниями с повторениями называется неупорядоченная -выборка, в которой элементы могут повторяться.
Пример 6. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Решение. Мощность мультимножества , число различных элементов . Число способов покупки пирожных равно .
6. Свойства чисел . Треугольник Паскаля.
Числа обладают целым рядом замечательных свойств, которые выражают различные соотношения между -подмножествами -множества .
1) . Это свойство непосредственно следует из определения чисел : .
2) .
Для доказательства поставим в соответствие подмножеству его дополнение . Это соответствие взаимно-однозначное. При этом, если , то . Следовательно, по принципу биекции число подмножеств, составленных из элементов столько же, сколько подмножеств, составленных из элементов.
Формально это свойство вытекает также из формулы (6).
3) .
Для доказательства разобьем все -элементные подмножества множества на два класса:
а) подмножества, не содержащие элемент . Это будут -элементные подмножества -множества, поэтому число их равно ;
б) подмножества, содержащие элемент . Если из каждого такого подмножества удалить элемент , то получим -элементные подмножества -множества, число которых равно . Свойство 3) вытекает, таким образом, из правила сложения.
При имеем . Так как , то полагают . Кроме того, придерживаются соглашения при . Тогда свойство 3) позволяет последовательно вычислить числа при . Вычисления представляют в виде треугольника Паскаля по имени французского математика Б. Паскаля (1623 – 1662), в трудах которого он применяется. Это название исторически неточно, так как такую таблицу знал уже арабский математик Омар Хайям (XIII в.). Этот треугольник имеет вид:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
……………………………………………..
7. Задача о беспорядках.
Сколькими способами можно разместить элементов множества в ячеек множества (по одному в каждой) так, чтобы никакой элемент не попал в ячейку ?
Перестановку без повторений можно представить как биекцию множества на себя:
.
Перестановку называют беспорядком, если в ней каждый элемент стоит не на своем месте, то есть , .
Задача о беспорядках состоит в том, чтобы подсчитать число перестановок-беспорядков. Например, , .
Обозначим через множество все перестановок , в которых элемент стоит на -ом месте:
.
Множество состоит из перестановок, в которых хотя бы один элемент стоит на своем месте, а все остальные перестановки будут беспорядками. Тогда по формуле обращения .
Подсчитаем число перестановок в каждом из множеств и в их пересечениях. Если , то сужение отображения на множество является биекцией этого множества на себя. Следовательно, .
Множество составлено из перестановок , в которых , . Сужение отображения на множество является биекцией этого множества на себя. Следовательно, .
По индукции находим, что .
По формуле включений и исключений
В каждой из этих сумм слагаемые не зависят от индекса суммирования, поэтому для вычисления надо знать только их количество. В первой сумме слагаемых, число слагаемых во второй сумме равно количеству всевозможных пар , которые можно составить из индексов , то есть . Аналогично в -ой сумме имеем слагаемых. Отсюда
.
После подстановки в уравнение (8) и несложных преобразований находим
.
Выражение, стоящее в скобках, представляет собой частичную сумму ряда, сходящегося к , поэтому . Можно показать, что равно целому числу, ближайшему к : , где – целая часть числа .
8. Определение рекуррентного соотношения, его частного и общего решения. Примеры: числа Фибоначчи, число правильных -разрядных двоичных слов, задача о расстановке скобок в выражении с неассоциативной бинарной операцией.
Рекуррентным соотношением -го порядка между элементами последовательности чисел называется формула вида (1)
Частным решением рекуррентного соотношения является любая последовательность , обращающая соотношение (1) в тождество. Соотношение (1) имеет бесконечно много частных решений, так как первые элементов последовательности можно задать произвольно. Например, последовательность является решением рекуррентного соотношения , так как имеет место тождество .
Решение рекуррентного соотношения -го порядка называется