Лекция: Комбинаторика. Понятие множества. Перестановки. Размещения. Сочетания.
Часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Разные пути или варианты, которые приходится выбирать, складываются в самые разнообразные комбинации. Целый раздел математики, называемый комбинаторикой, занят поиском ответов на вопросы: сколько всего есть комбинаций в том или другом случае.
Определение.Число различных способов, которыми может быть упорядочено данное множество, состоящее из элементов, называется числом перестановок множества и обозначается . Число перестановок из элементов вычисляется следующим образом:
(21.1.)
Определение.Количество перестановок из элементов, среди которых имеется одинаковых элементов первого сорта, одинаковых элементов второго сорта, одинаковых элементов k-го сорта, называется количеством перестановок с повторениями, обозначается символом. Число перестановок с повторениями вычисляется по формуле
(21.2)
Пусть задано некоторое конечное множество из различных элементов. Пусть из числа его элементов выбраны различных штук ( ), тогда говорят, что произведена выборка объёма. Если важен порядок, в котором произведена выборка элементов, то говорят об упорядоченной выборке, если порядок не важен, то о неупорядоченной выборке.
Определение. Упорядоченная выборка объёма из множества, состоящего из элементов, ( ) называется размещением из элементов по и обозначается .
Количество размещений из элементов по вычисляется следующим образом:
(21.3)
Познакомившись с размещением вернемся к понятию перестановки.
Определение.Размещение из элементов по называется перестановкой из элементов и обозначается .
Другими словами,
Определение. Упорядоченная выборка объёма из множества, состоящего из элементов называется размещением с повторениемиз элементов по и обозначаются .
Количество размещений с повторениями вычисляется по формуле
(21.4)
Допустим теперь, что нас не интересует порядок, в котором идут выбранные элементы. Например, нужно из десяти человек выбрать троих дежурных. Такая операция называется неупорядоченной выборкой, или сочетанием, в отличие от упорядоченной выборки – размещения.
Определение. Всякая неупорядоченная выборка объёма из множества, состоящего из элементов, ( ) называетсясочетанием из элементов по и обозначается .
Количество сочетаний из элементов по вычисляется по формуле
(21.5)
Как и в случае с размещениями, существует понятие числа сочетаний с повторениями.
Определение.Если из множества, содержащего n элементов, выбирается поочередно m элементов, причём выбранный элемент каждый раз возвращается обратно, то количество способов произвести неупорядоченную выборку называется сочетанием с повторениями и обозначается .
Количество способов произвести неупорядоченную выборку – число сочетаний с повторениями составляет
(21.6)