Размещения
Всякий упорядоченный набор имеющий $k$ элементов, взятых из наперед заданных $n$ элементов без повторений, будем называть размещением из $n$ по $k$.
Математически, такое размещение обозначается следующим образом:
$A_n^k$
Введем далее формулу для нахождения значения такого размещения в виде теоремы.
Значение размещения из $n$ по $k$ находится следующим образом:
$A_n^k=\frac{n!}{(n-k)!}$
Доказательство.
Так как всего мы имеем $n$ элементов, то при составлении таких упорядоченных наборов на первое место мы можем выбрать каждый из них. То есть на первое место выбирать элемент мы можем $n$ количеством способов.
Теперь у нас осталось $n-1$ элементов. Значит, на второе место выбирать элемент мы можем $n-1$ количеством способов.
Далее, при выборе количества способов на каждое последующее место рассуждаем аналогично.
На последнее $k$-е место выбирать элемент мы можем $n-(k-1)$ количеством способов.
По правилу произведения мы, в результате, получаем:
$A_n^k=n(n-1)(n-2)…(n-k+1)$
Умножив и разделив на $(n-k)!$, получим
$A_n^k=\frac{n(n-1)(n-2)…(n-k+1)(n-k)…2\cdot 1}{(n-k)!}=\frac{n!}{(n-k)!}$
Теорема доказана.
Статья: Основные понятия комбинаторики
Приведем пример решения задачи с помощью этого понятия.
В вагоне метро свободно четыре посадочных места. На станции в него зашло $3$ человека. Сколькими способами они могут разместиться сидя в этом вагоне?
Решение.
Здесь нам нужно разместить три человека на четыре свободных сидячих места. Значит, эта задача на нахождение размещения из четырех по три. Получим
$A_4^3=\frac{4!}{(4-3)!}=\frac{24}{1!}=24$
Ответ: $24$.
Перестановки
Всякий упорядоченный набор имеющий $n$ элементов, взятых из наперед заданных $n$ элементов без повторений, будем называть перестановкой из $n$.
Математически, такая перестановка обозначается следующим образом:
$P_n$
Введем далее формулу для нахождения значения такой перестановки в виде теоремы.
Значение перестановки из n находится следующим образом:
$P_n=n!$
Доказательство.
Очевидно, что перестановка является частным случаем для размещения в случае размещения из $n$ по $n$. Следовательно
$P_n=A_n^n=\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!$
Теорема доказана.
Приведем пример решения задачи с помощью этого понятия.
Нам нужно повесить на доску три объявления на три свободных места. Сколькими способами мы можем повесить эти три объявления?
Решение.
Здесь нам нужно разместить три объявления на столько же свободных мест. Значит, эта задача на нахождение перестановок из трех. Получим
$P_3=3!=6$
Ответ: $6$.
Сочетания
Всякий неупорядоченный набор имеющий $k$ элементов, взятых из наперед заданных $n$ элементов без повторений, будем называть сочетанием из $n$ по $k$.
Математически, такое сочетание обозначается следующим образом:
$C_n^k$
Введем далее формулу для нахождения значения такого сочетания в виде теоремы.
Значение сочетания из $n$ по $k$ находится следующим образом:
$C_n^k=\frac{n!}{(n-k)!k!}$
Доказательство.
Так как сочетания является неупорядоченным набором, а размещение упорядоченным, то по каждому сочетанию можно получить точно $k!$ размещений по тем же элементам. То есть количество сочетаний обратно пропорционально количеству размещений по тем же элементам с коэффициентом пропорциональности $k!$. То есть, получаем
$C_n^k=\frac{A_n^k}{k!}=\frac{n!}{(n-k)!k!}$
Теорема доказана.
Приведем пример решения задачи с помощью этого понятия.
В корзине лежат $12$ разных зерен для высадки цветов. Нам нужно посадить всего $4$. Сколькими способами мы можем выбрать, какие посадить?
Решение.
Здесь, по сути, нам просто нужно вытащить из корзины $4$ наугад попавшиеся зерна. То есть здесь мы имеем дело с сочетанием из $12$ зерен по $4$.
Получаем:
$C_n^k=\frac{12!}{(12-4)!4!}=\frac{12!}{8!4!}=\frac{9\cdot 10\cdot 11\cdot 12}{1\cdot 2\cdot 3\cdot 4}=495$
Ответ: $495$.
