Блог Джафара Алиева

Архив

Домашняя страница :: Другие статьи :: Аналитика


Дата создания:

Размещение, перестановка, сочетание

комбинаторика  

 

Размещение

Если из множества $n$ различных элементов выбирать комбинацию из $k$ штук так, чтобы они отличались элементами или порядком, то мы получим размещение (на франц. arrangement) из $n$ элементов по $k$. Такое размещение обозначается как $A_n^k$. Понятно, что $k \leqslant n$.

Допустим, нам нужно составить все возможные размещения из двух элементов множества $\{a, b, c\}$. Так как это маленькое множество, все такого рода размещения из двух элементов можно написать без труда.

$ab$, $ac$, $ba$, $bc$, $ca$, $cb$

Как видно, здесь каждое подмножество участвует по два раза. $ab$ и $ba$, $bc$ и $cb$, $ac$ и $ca$ являются одним и тем же подмножеством, но они различны с точки зрения размещения.

Теорема: Число размещений $n$ элементов по $k$ вычисляется следующим образом.

$A_n^k = n(n-1) … (n-k+1)$

Доказательство: Допустим, дано множество  $\{a_1, a_2, …, a_n\}$. Нам нужно составить все размещения $\{a_{i_1}, a_{i_2}, …, a_{i_k}\}$. Чтобы построить такие размещения сначала выберем первый элемент $a_{i_1}$. Понятно, что $a_{i_1}$ можно выбирать $n$ различным образом. В каждом случае второй элемент можем выбирать из оставшихся $n-1$ элементов. Итак, для выбора первого и второго элементов мы имеем $n(n-1)$ вариантов размещения. Зафиксировав первый и второй элемент, третий элемент можем выбрать из оставшихся $n-2$ элементов. Продолжая это рассуждение для выбора $k$ элементов, получим $n(n-1)…(n-k+1)$ вариантов.

Размещение с повторениями

При размещении с повторениями выбирая $k$ элементов из $n$, мы позволяем выбирать один и тот же элемент несколько раз. Как будто после каждого выбора мы возвращаем выбранный элемент в основное множество. Здесь каждый элемент из $\{a_1, a_2, …, a_n\}$ может участвовать заново в выборке.

Объясним это на примере множества $\{a, b, c\}$.Рассмотрим все возможные размещения с повторениями из двух элементов.

$aa$, $ab$, $ac$, $ba$, $bb$, $bc$, $ca$, $cb$, $cc$

Как видно, здесь всего $9$ вариантов.

Теорема: Число всех размещений с повторениями из $n$ элементов по $k$ равно $n^k$.

Доказательство: Доказательство проведем с помощью индукции. Если $k=1$, то понятно, что всего возможно $n$ вариантов. Значит $n^1=n$.

Теперь допустим что теорема верна для случая $k$ и докажем для $k+1$. Допустим, число всевозможных размещений с повторениями из множества $\{a_1, a_2, …, a_n\}$ по $k$ элементов, равно $n^k$. Для случая $k+1$, мы добавим $k+1$-й элемент в каждую из $n^k$ размещений с повторениями. А $k+1$-й элемент мы выбираем среди $n$ элементов. Значит, всего $n$ возможных значений $k+1$-го элемента сочетаются с $n^k$ возможными размещениями. А это значит, для $k+1$ получим $n^k \cdot n = n^{k+1}$ размещений с повторениями.

Примером такого размещения может быть трехзначный замок, где каждая цифра меняется от $0$ до $9$. Количество всех комбинаций равно $10^3=1000$.

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

Расположение элементов множества в определенном порядке называется перестановкой (на франц. permutación).

На примере множества $\{a, b, c\}$ это будут следующие $6$ наборов перестановок.

$abc$, $acb$, $bca$, $bac$, $cab$, $cba$

Теорема: Количество всех перестановок множества из $n$ элементов равно
$$P_n = n!$$

Доказательство: Перестановка является частным случаем размещения, когда $k=n$. Тогда по формуле размещения

$A_n^n = n(n-1)(n-2) … (n-n+1) = n!$

Сочетание

Сочетаниями (на франц. combinaison) из $n$ элементов по $k$ называются комбинации из $k$ различных элементов множества. В этих наборах не должно быть повторений. Если рассмотрим все такие наборы, то сюда не включаются те, что отличаются только порядком элементов. Это и является отличием сочетаний от размещений.

На примере множества $\{a, b, c\}$ все сочетания из двух элементов выглядят так.

$ab$, $ac$, $bc$

Теорема: Число сочетаний из $n$ элементов по $k$ вычисляется так.

$$C_n^k = \dfrac{n(n-1) … (n-k+1)}{k!}$$

Доказательство: Выбирая $k$ элементов из $n$, по определению получим $C_n^k$ сочетаний. В каждом таком сочетании эти $k$ элементов участвуют только один раз. Если сюда включим их перестановку, то это количество возрастет в $P_k$ раз. В результате получим все размещения из $n$ элементов по $k$.

$A_n^k=C_n^k \cdot P_k \Rightarrow \\[15pt]
\Rightarrow C_n^k=\dfrac{A_n^k}{P_k}=\dfrac{n(n-1) … (n-k+1)}{k!}$

Эту формуле можно написать следующим образом, умножая числитель и знаменатель на $(n-k)!$

$C_n^k = \dfrac{n!}{k!(n-k)!}$

Читайте также

Биномиальное распределение
Биномиальное распределение является одним из видов дисретного распределения, т.е. является распределением вероятностей случайной величины из ограниченного количества значений. Биномиальное распределение применяется к дихотомическим данным.

© Все права защищены

Все статьи этого сайта написаны Джафаром Н.Алиевым. Перепечатывание любой статьи на стороннем ресурсе должно сопровождаться именем автора и ссылкой на данный ресурс. Сам автор следует этим правилам.