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) имеет бесконечно много частных решений, так как первые элементов последовательности можно задать произвольно. Например, последовательность является решением рекуррентного соотношения , так как имеет место тождество .Решение рекуррентного соотношения -го порядка называется

---

Смотрите также файлы

• Правила проектирования и оформления проектов стандартизованы в Единой системе конструкторской документации (ескд), которая устанавливает пять стадий разработки конструкторской документации.pptx

• Министерство образования и науки государственное образовательное учреждение высшего профессионального образования.docx

• Закон противоречия и споры вокруг него.docx

• Основная образовательная программа начального (основного) общего образования. 1)срок получения ооо 5 лет (не установлено сокращение).docx

• Темам 4 Тема Практическое занятие Требования к соблюдению основных принципов работы психолога Ситуация 4.docx