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

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

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

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

Если элемент $a$ может быть выбран из множества элементов $n$ способами и при любом таком выборе элемент $b$ может быть выбран $m$ способами, то пара $(a,b)$ может быть выбрана $n\cdot m$ способами.

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

Если элемент $a$ может быть выбран из множества элементов $n$ способами, а элемент $b$ может быть выбран $m$ способами, то выбрать $a$ или $b$ можно $n+m$ способами.

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

Перестановка

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

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

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

Число всевозможных перестановок (без повторений) из $n$ элементов равно

$P_{1}=n(n-1)(n-2)\cdot \ldots \cdot 3\cdot 2\cdot 1=n!$, где $n!$ называется факториалом числа $n$. По определению, $0!=1$.

Если среди $n$ элементов $a_{1},a_{2},a_{3},\ldots ,a_{n}$ имеются одинаковые, причем $a_{1}$ повторяется $k_{1}$ раз, $a_{2}$ — $k_{2}$ раз, \ldots, $a_{n}$ — $k_{n}$ раз, то число таких перестановок с повторениями равно

${\bar {P}}_{n}={\frac {n!}{k_{1}!\cdot k_{2}!\cdot \ldots \cdot k_{n}!}}$.

Размещение

Размещением без повторений из $n$ элементов данного множества по $k$ называется упорядоченный набор из $k$ различных элементов, выбранных из данных элементов

Перестановка также является размещением из $n$ элементов по $n$.

Число всемозможных размещений (без повторений) из $n$ элементов по $k$ равно

$A_{n}^{k}=n(n-1)\cdot \ldots \cdot (n-k+1)={\frac {n!}{(n-k)!}}$

Размещения могут отличаться друг от друга как составом элементов, так и их порядком

Если при размещении $n$ элементов по $k$ каждый элемент может повторяться сколько угодно раз, то число таких размещений с повторением равно

${\bar {A}}_{n}^{k}=n^{k}$.

Сочетание

Трёхэлементные подмножества пятиэлементного набора

Сочетанием из $n$ элементов по $k$ называется набор $k$ элементов, выбранных из данных $n$ элементов, которые отличаются хотя бы одним элементом.

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

Число всевозможных сочетаний из $n$ элементов по $k$ равно

$C_{n}^{k}={\frac {n!}{k!(n-k)!}}$.

Основные свойства сочетаний:

$C_{n}^{k}=C_{n}^{n-k},\qquad C_{n}^{k}+C_{n}^{k+1}=C_{n+1}^{k+1}$

Примеры

Пример 1

Дано множество, состоящее из трех элементов {1, 2, 3}. Найти число всевозможных: а) перестановок, б) размещений по два элемента (с повторениями и без), в) сочетаний по два элемента.

Решение:

а) Так как в данном множестве элементы не повторяются, то всевозможными перестановками без повторений являются наборы (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2). Число таких перестановок равно $P_{3}=3!=6$

б) Различными размещениями без повторений из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2). Число таких размещений равно $A_{3}^{2}=3\cdot 2=6$

Различными размещениями с повторениями из трех элементов {1, 2, 3} по два будут наборы (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3). Число таких размещений равно ${\bar {A}}_{3}^{2}=3^{2}=9$

в) Различными сочетаниями из трех элементов {1, 2, 3} по два будут наборы {1, 2}, {1, 3}, {2, 3}. Число таких сочетаний равно $C_{3}^{2}={\frac {3!}{2!\cdot 1!}}=3$

Пример 2

Сколько четырехзначных чисел можно составить из цифр, не равных нулю?

Решение:

Всего цифр, не равных нулю, 9. Число всевозможных чисел равно числу размещений с повторениями и находится по формуле $A_{9}^{4}=9^{4}=6561$

Пример 3

Сколькими способами можно разложить два различных шара (черный и белый) по трем ящикам, если в любой ящик можно положить не более одного шара?

Решение:

Первый шар можно положить в один из трех ящиков тремя способами. Затем второй шар можно положить в оставшиеся 2 ящика двумя способами. Число способов разложить два различных шара равно $A_{3}^{2}=3\cdot 2=6$

Пример 4

Сколькими способами из 9 человек можно выбрать комиссию из трех человек?

Решение:

Состав комиссии должен отличаться хотя бы одним человеком. Следовательно, число способов выбрать комиссию равно $C_{9}^{3}={\frac {9!}{3!\cdot 6!}}=84$

Упражнения

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

	$P_{n}=(n-1)!$
	$P_{n}=n!$
	$P_{n}={\frac {n!}{(n-k)!}}$

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

	${\bar {A}}_{n}^{k}=n^{k}$
	${\bar {A}}_{n}^{k}=k^{n}$.
	${\bar {A}}_{n}^{k}=n\cdot k$.

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

	$C_{n}^{k}=k!\cdot (n-k)!$
	$C_{n}^{k}=C_{n}^{n-k}$
	$C_{n}^{k}+C_{n}^{k+1}=C_{n+1}^{k+1}$