Разбиением множества называется всякое представление этого множества в виде суммы непересекающихся подмножеств:

, .

Здесь – множество индексов, которое может быть конечным, счетным или несчетным. Множества называют слоями разбиения.

Имеет место следующая теорема.

Теорема 2. Для того чтобы отношение позволяло разбить множество на классы, необходимо и достаточно, чтобы было отношением эквивалентности.

Приведем примеры использования отношения эквивалентности для образования математических понятий.

1. 
   Понятие вектора. Сначала вводится понятие направленного отрезка, как пары точек . Два отрезка и объявляются эквивалентными, если середины отрезков и совпадают. Далее проверяется, что это отношение между направленными отрезками рефлексивно, симметрично и транзитивно. Класс эквивалентных отрезков и есть вектор.
   
2. 
   Построение рациональных чисел из целых. Рассмотрим всевозможные пары из целых чисел такие, что . Пары и объявляются эквивалентными, если . Далее проверяется рефлексивность, симметричность и транзитивность. Класс эквивалентных пар – рациональное число.
   

Отношение порядка. Бинарное отношение на множестве называется отношением порядка, если оно рефлексивно, транзитивно и антисимметрично. Последнее свойство означает: .

Пример 5. Примеры отношений порядка:

– отношение « » на множестве действительных чисел. Отношение « » порядком не является, так как оно не рефлексивно;

– отношение « » на множестве подмножеств некоторого множества;

– на множестве двоичных слов длины можно ввести отношение порядка следующим образом. Пусть и – двоичные слова. Положим , если для , 1, 2, …, .

Пусть – отношение порядка на множестве . Элементы называются сравнимыми, если или , в противном случае – несравнимыми.

Порядок называется линейным, если любые два элемента сравнимы. В противном случае говорят о частичном порядке. Множество с заданным на нем порядком (частичным или линейным) называется упорядоченным (частично или линейно). Первое отношение в примере 5 задает линейный порядок, два других отношения порядка – частичные. Например, двоичные слова 011 и 110 несравнимы.

Элемент частично упорядоченного множества называется максимальным (минимальным), если из того, что следует . Элемент называется наибольшим (наименьшим), если ( ) для всех .

Верхней (нижней) гранью подмножества частично упорядоченного множества называется такой элемент , что

---

( ).

Точной верхней (нижней) гранью подмножества называется наименьшая верхняя (наибольшая нижняя) грань для . Точная верхняя и точная нижняя грани обозначаются соответственно и .

Линейный порядок на множестве называется полным, если каждое непустое подмножество множества имеет наименьший элемент. В этом случае множество называется вполне упорядоченным.

Частично упорядоченное множество называется решёткой, или структурой, если для любых двух элементов существует точная нижняя и точная верхняя грани.

Пример 6. Примеры решёток:

– множество всех подмножеств данного множества, упорядоченное по включению;

– всякое линейно упорядоченное множество; причем, если , то .

4. Общие правила комбинаторики: правила суммы, произведения и биекции. Булеан

конечного множества. Примеры.

Правило суммы

Это правило позволяет найти число элементов в объединении двух конечных множеств и :

. (1)

Если множества и не пересекаются ( ), то

. (2)

Иногда правило суммы формулируют следующим образом:

если объект можно выбрать способами, а объект – способами, то выбор «либо , либо » можно осуществить способами.

Пример 1. Сколько имеется путей из вершины в вершину на решетке, показанной на рис. 1?

Рис.1. Решетка размером [4 5]

Обозначим множество всех путей из в через и разобьем его на два непересекающиеся подмножества: – множество путей, проходящих через вершину , – множество путей, проходящих через вершину . Тогда .

Очевидно, что искомое количество путей зависит только от размеров решетки. Обозначим через количество путей в решетке размером [ ], где , – соответственно количество горизонтальных и вертикальных путей. Тогда причем . Пользуясь этим соотношением для данного примера , , получим:

.

Правило произведения

Это правило позволяет подсчитать число кортежей, которые можно составить из элементов данных конечных множеств. Для двух множеств и

(3)

Из равенства (3) следует, что число упорядоченных пар, которые можно составить из элементов множеств и равно произведению числа элементов в этих множествах.

_{Это правило можно сформулировать иначе:}

если объект можно выбрать способами и после каждого из таких выборов другой объект можно выбрать способами, то выбор «

---

и » можно осуществить способами.

По индукции правило умножения можно распространить на любое число сомножителей в декартовом произведении:

. (4)

Наиболее часто последнее равенство применяется, когда :

. (5)

В этом случае множество называют алфавитом, его элементы – буквами, а элементы декартова произведения – словами в алфавите . Слова записывают как в обычном языке, то есть без разделения букв запятыми и без внешних скобок: . Число называют длиной слова.

Пусть . Тогда правило (5) можно сформулировать следующим образом:

число слов длины в алфавите из букв равно .

Пример.2. Из 80 студентов 40 играют в футбол, а 50 – в волейбол, причем 27 студентов играют и в футбол и в волейбол. Сколько студентов играют хотя бы в одну из этих игр? Сколько студентов играют лишь в одну из этих игр? Сколько студентов не играют ни в одну из этих игр?

Пусть – множество студентов, играющих в футбол, – множество студентов, играющих в волейбол. Тогда , , .

Число студентов, играющих хотя бы в одну из этих игр, согласно формуле (2.1): . Число студентов, играющих только в футбол: , а только в волейбол: . Число студентов, играющих только в одну из этих игр: . Число студентов, не играющих ни в одну из этих игр: .

Пример 3. Сколько существует 6-значных телефонных номеров?

Алфавит состоит из 10 цифр, номер – слово длины 6 в этом алфавите. Поэтому количество номеров равно .

Пример 4. Найти число слов, содержащих 4 буквы, в которых любые две соседние буквы различны (число букв в алфавите равно 33).

Первую букву можно выбрать 33-мя способами, вторую, третью и четвертую – 32 способами. Число слов равно 33∙32³=1081344.

---

Правило биекции

Это правило, которое называется также принципом взаимно однозначного соответствия, формулируется следующим образом:

если между множествами и можно установить взаимно однозначное соответствие (биекцию), то .

В качестве примера применения этого принципа найдем мощность множества всех подмножеств данного множества . Такое множество называют булеаном множества и обозначают символом .

Пусть – -множество. Так как мощность множества не зависит от природы его элементов, то можно принять .

Поставим в соответствие произвольному подмножеству двоичное слово по следующему правилу:

Это соответствие взаимно однозначное. Отсюда следует, что число всех подмножеств -множества равно числу двоичных слов длины , то есть .
5. Метод включений и исключений. Пример.

Поставим задачу подсчитать количество элементов в объединении конечных множеств , которые могут иметь непустые пересечения между собой, т. е. это объединение в общем случае не является разбиением.

Для двух множеств имеем формулу (1). Обозначим и применим эту формулу для трех множеств, используя дистрибутивность операций объединения и пересечения множеств:

(6)

В результате по индукции получаем формулу включений и исключений:

(7)
Подсчитаем теперь число элементов , обладающих ровно свойствами. Покажем, что в этом случае имеет место следующая формула включений и исключений:

. (9)

Действительно, элемент, обладающий ровно , , свойствами, не будет учитываться в формуле (9), а элемент, обладающий ровно свойствами, будет учитываться только один раз, так как

При из формулы (9), как частный случай, имеем формулу обращения (8). Использование формулы (9) в комбинаторике называют методом включений и исключений.

Пример 6. Найти число перестановок -множества, оставляющих на месте ровно элементов.

Решение. Перестановки элементов данного -множества будем считать элементами -множества. Обозначим и свойство перестановки, состоящее в том, что элемент с номером в результате данной перестановки остается на месте. Тогда

, .

По формуле (9)

. (10)
6. Понятие выборки. Размещения и формулы для их подсчета с повторениями и без

повторений элементов. Примеры.

7. Понятие выборки. Перестановки и формулы для их подсчета с повторениями и без

---

повторений элементов. Примеры.

8. Понятие выборки. Сочетания и формулы для их подсчета с повторениями и без

повторений элементов. Примеры.

Понятие выборки

Набор элементов из множества называется выборкой объема из элементов или -выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней задан. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов не является существенным, то выборка называется неупорядоченной. В выборках могут допускаться или не допускаться повторения элементов. В зависимости от способа формирования все выборки в комбинаторике классифицируют как размещения, перестановки и сочетания с повторениями и без повторений элементов.

Размещения

-размещением с повторениями из элементов называется упорядоченная -выборка, в которой элементы могут повторяться. Число всех таких выборок, которые отличаются друг от друга составом элементов или их порядком, равно числу векторов в декартовом произведении . Это число обозначают . По правилу произведения получаем

. (1)

Пример 1. Для запирания сейфа используется диск, на который нанесены 12 символов, а секретное слово состоит из 5 символов. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова?

Общее число комбинаций равно . Значит, неудачных попыток может быть 248831.

-размещением без повторений из элементов называется упорядоченная -выборка, в которой элементы не повторяются. Число всех упорядоченных -множеств с различными элементами, которые можно составить из элементов -множества , обозначают .

Для вычисления необходимо сделать выборов. 1-й элемент можно выбрать способами, 2-й – ( ) способами и т. д. Последний -й элемент можно выбрать способами. По правилу произведения

. (2)

Здесь – « -факториал» (0!=1!=1).

Пример 2. Научное общество состоит из 25 человек. Надо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост?

Ответ: .
Перестановки
Решим следующую комбинаторную задачу.

Сколькими способами можно упорядочить -множество ?

Перестановками без повторений

---

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

• Компоненты интегрированной среды разработки программ.docx

• Доклад по теме самообразования Развитие творческих способностей на уроках в начальной школе.docx

• Инструкция по охране труда для учителя физики. Инструкция по охране труда и технике безопасности для лаборанта кабинета физики.odt

• Учебное пособие Москва 2021 Одобрено редакционноиздательским советом Академии управления мвд россии Рецензенты.pdf

• Изучение технологии и оборудования шовной контактной сварки (на примере машины мш1601).docx