Комбинаторика. Понятие множества. Перестановки. Размещения. Сочетания.

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

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

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

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

Множество, состоящее из элементов, называется упорядоченным, если каждому элементу этого множества поставлено в соответствие натуральное число (номер) от 1 до таким образом, что различным элементам соответствуют различные натуральные числа.

Всякое конечное множество можно упорядочить.

Множества обозначаются большими латинскими буквами, а их элементы — малыми ( означает, что a есть элемент множества A или элемент a принадлежит множеству A).

Количество элементов конечного множества обозначается N(A).

Если каждый элемент множества B принадлежит множеству A, то B называется подмножеством множества A ().

Если задано некоторое множество A, то можно рассматривать новое множество M(A) — множество всех его подмножеств. Через будем обозначать множество всех подмножеств A, которые имеют k элементов: , если и .

Итак, множество является тем, что имеет элементы, а элементы это то, что-либо входит, либо не входит в данное множество. В множестве не может быть двух или более одинаковых элементов, а порядок расположения элементов в множестве не имеет никакого значения. Обозначим некоторое множество символом , а все элементы, входящие в это множество, — символами . Тогда запись означает, что множество содержит только те и только те элементы , которые указаны в фигурных скобках. Напомним, что все элементы различны, а их порядок указания в фигурных скобках не имеет значения.

Над множествами можно выполнять различные операции: объединение (), пересечение (), вычитание () и пр.

Объединение множеств и есть множество, обозначаемое как , которое содержит все элементы множества и все элементы множества .

Задача 21.1. , . Найдите _.

Решение. .

Напомним, что в любом множестве все элементы должны быть различны. Другими словами, множество содержит только такие элементы, которые принадлежат множеству или множеству (возможно, и обоим одновременно). В частности, .

Пересечение множеств и есть множество, обозначаемое как , которое содержит все элементы, принадлежащие как множеству , так и множеству . Если таких элементов нет, то пересечение множеств пусто ().

Задача 21.2. , . Найдите .

Решение. .

В частности, .

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

Задача 21.3. Пусть , . Найдите .

Решение. .

В частности, .

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

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

(21.1.)

Определение. Количество перестановок из элементов, среди которых имеется одинаковых элементов первого сорта, одинаковых элементов второго сорта, одинаковых элементов k -го сорта, называется количеством перестановок с повторениями, обозначается символом . Число перестановок с повторениями вычисляется по формуле

(21.2)

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

Определение. Упорядоченная выборка объёма из множества, состоящего из элементов, () называется размещением из элементов по и обозначается .

Количество размещений из элементов по вычисляется следующим образом:

(21.3)

Познакомившись с размещением вернемся к понятию перестановки.

Определение. Размещение из элементов по называется перестановкой из элементов и обозначается .

Другими словами,

Определение. Упорядоченная выборка объёма из множества, состоящего из элементов называется размещением с повторением из элементов по и обозначаются .

Количество размещений с повторениями вычисляется по формуле

(21.4)

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

Определение. Всякая неупорядоченная выборка объёма из множества, состоящего из элементов, () называется сочетанием из элементов по и обозначается .

Количество сочетаний из элементов по вычисляется по формуле

(21.5)

Как и в случае с размещениями, существует понятие числа сочетаний с повторениями.

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

Количество способов произвести неупорядоченную выборку – число сочетаний с повторениями составляет

(21.6)