Теория вероятностей и математическая статистика/Элементы комбинаторики

Комбинаторика изучает способы подсчета количества комбинаций, подчиненных тем или иным условиям, которые можно составить из заданного конечного множества объектов. Формулы комбинаторики используют при решении многих задач теории вероятностей.

Основные правила комбинаторики править

Правило умножения править

Если элемент   может быть выбран из множества элементов   способами и при любом таком выборе элемент   может быть выбран   способами, то пара   может быть выбрана   способами.

Правило суммы править

Если элемент   может быть выбран из множества элементов   способами, а элемент   может быть выбран   способами, то выбрать   или   можно   способами.

Основные формулы комбинаторики править

Перестановка править

 
В популярной головоломке «Кубик Рубика», изобретенной в 1974 году Эрно Рубиком, каждый поворот граней головоломки создает перестановку цветов поверхности.

Пусть имеется множество, состоящее из   элементов.

Перестановкой без повторений из   элементов данного множества называется всякий упорядоченный набор из этих 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 человек можно выбрать комиссию из трех человек?

Решение:

Состав комиссии должен отличаться хотя бы одним человеком. Следовательно, число способов выбрать комиссию равно  

Упражнения править

1 Какая из данных формул является формулой подсчета перестановки без повторений?

 
 
 

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

 
 .
 .

3 Выберите верные утверждения?