Теория вероятностей и математическая статистика/Элементы комбинаторики
Комбинаторика изучает способы подсчета количества комбинаций, подчиненных тем или иным условиям, которые можно составить из заданного конечного множества объектов. Формулы комбинаторики используют при решении многих задач теории вероятностей.
Основные правила комбинаторики
правитьПравило умножения
правитьЕсли элемент может быть выбран из множества элементов способами и при любом таком выборе элемент может быть выбран способами, то пара может быть выбрана способами.
Правило суммы
правитьЕсли элемент может быть выбран из множества элементов способами, а элемент может быть выбран способами, то выбрать или можно способами.
Основные формулы комбинаторики
правитьПерестановка
правитьПусть имеется множество, состоящее из элементов.
Перестановкой без повторений из элементов данного множества называется всякий упорядоченный набор из этих n элементов.
Число всевозможных перестановок (без повторений) из элементов равно
, где называется факториалом числа . По определению, .
Если среди элементов имеются одинаковые, причем повторяется раз, — раз, \ldots, — раз, то число таких перестановок с повторениями равно
.
Размещение
правитьРазмещением без повторений из элементов данного множества по называется упорядоченный набор из различных элементов, выбранных из данных элементов
Перестановка также является размещением из элементов по .
Число всемозможных размещений (без повторений) из элементов по равно
Размещения могут отличаться друг от друга как составом элементов, так и их порядком
Если при размещении элементов по каждый элемент может повторяться сколько угодно раз, то число таких размещений с повторением равно
.
Сочетание
правитьСочетанием из элементов по называется набор элементов, выбранных из данных элементов, которые отличаются хотя бы одним элементом.
В сочетаниях наборы, отличающиеся только порядком следования элементов(но не составом), считаются одинаковыми, в отличие от размещений.
Число всевозможных сочетаний из элементов по равно
.
Основные свойства сочетаний:
Примеры
правитьПример 1
правитьДано множество, состоящее из трех элементов {1, 2, 3}. Найти число всевозможных: а) перестановок, б) размещений по два элемента (с повторениями и без), в) сочетаний по два элемента.
Решение:
а) Так как в данном множестве элементы не повторяются, то всевозможными перестановками без повторений являются наборы (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2). Число таких перестановок равно
б) Различными размещениями без повторений из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2). Число таких размещений равно
Различными размещениями с повторениями из трех элементов {1, 2, 3} по два будут наборы (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3). Число таких размещений равно
в) Различными сочетаниями из трех элементов {1, 2, 3} по два будут наборы {1, 2}, {1, 3}, {2, 3}. Число таких сочетаний равно
Пример 2
правитьСколько четырехзначных чисел можно составить из цифр, не равных нулю?
Решение:
Всего цифр, не равных нулю, 9. Число всевозможных чисел равно числу размещений с повторениями и находится по формуле
Пример 3
правитьСколькими способами можно разложить два различных шара (черный и белый) по трем ящикам, если в любой ящик можно положить не более одного шара?
Решение:
Первый шар можно положить в один из трех ящиков тремя способами. Затем второй шар можно положить в оставшиеся 2 ящика двумя способами. Число способов разложить два различных шара равно
Пример 4
правитьСколькими способами из 9 человек можно выбрать комиссию из трех человек?
Решение:
Состав комиссии должен отличаться хотя бы одним человеком. Следовательно, число способов выбрать комиссию равно
Упражнения
править