Разместить заказ
Вы будете перенаправлены на Автор24

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

8-800-775-03-30 support@author24.ru
Статья предоставлена специалистами сервиса Автор24
Автор24 - это сообщество учителей и преподавателей, к которым можно обратиться за помощью с выполнением учебных работ.
как работает сервис
Основные понятия комбинаторики

Размещения

Определение 1

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

Математически, такое размещение обозначается следующим образом:

$A_n^k$

Введем далее формулу для нахождения значения такого размещения в виде теоремы.

Теорема 1

Значение размещения из $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)!}$

Теорема доказана.

Приведем пример решения задачи с помощью этого понятия.

Пример 1

В вагоне метро свободно четыре посадочных места. На станции в него зашло $3$ человека. Сколькими способами они могут разместиться сидя в этом вагоне?

Решение.

Здесь нам нужно разместить три человека на четыре свободных сидячих места. Значит, эта задача на нахождение размещения из четырех по три. Получим

$A_4^3=\frac{4!}{(4-3)!}=\frac{24}{1!}=24$

Ответ: $24$.

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

Определение 2

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

Математически, такая перестановка обозначается следующим образом:

$P_n$

Введем далее формулу для нахождения значения такой перестановки в виде теоремы.

Теорема 2

Значение перестановки из n находится следующим образом:

$P_n=n!$

Доказательство.

Очевидно, что перестановка является частным случаем для размещения в случае размещения из $n$ по $n$. Следовательно

$P_n=A_n^n=\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!$

Теорема доказана.

Приведем пример решения задачи с помощью этого понятия.

Пример 2

Нам нужно повесить на доску три объявления на три свободных места. Сколькими способами мы можем повесить эти три объявления?

Решение.

Здесь нам нужно разместить три объявления на столько же свободных мест. Значит, эта задача на нахождение перестановок из трех. Получим

$P_3=3!=6$

Ответ: $6$.

Сочетания

Определение 3

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

Математически, такое сочетание обозначается следующим образом:

$C_n^k$

Введем далее формулу для нахождения значения такого сочетания в виде теоремы.

Теорема 3

Значение сочетания из $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!}$

Теорема доказана.

Приведем пример решения задачи с помощью этого понятия.

Пример 3

В корзине лежат $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$.