Математика → Теория → Справочник → Алгебра → Комбинаторика → Комбинаторика

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

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

Правила суммы и произведения

Правило суммы: если элемент можно выбрать различными способами и независимо от него элемент можно выбрать различными способами, то выбрать все различные комбинации элементов « или » можно сделать m + n способами.

Правило произведения: если элемент можно выбрать различными способами и независимо от него элемент можно выбрать различными способами, то все различные комбинации элементов « и » можно выбрать $m \cdot n$ способами.

Правила суммы и произведения естественным образом обобщаются и на случай комбинаций многих элементов, а именно, если первый элемент совокупности из различных элементов можно выбрать n_1 способами, второй — n_2 способами и так далее, -й элемент — n_k способами, то всевозможных комбинаций соответственно $n_1 + n_2 + \ldots + n_k$ и $n_1 \cdot n_2 \cdot \ldots \cdot n_k$ .

Факториал

Произведение первых натуральных чисел называется n-факториал и обозначается n!; По определению: 1! = 1;
0! = 1 .

Перестановки без повторений

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

Перестановкой из элементов (или -перестановкой) называется -элементное упорядоченное множество, составленное из элементов -элементного множества.

Иначе: Перестановкой из элементов (или -перестановкой) называется размещение из элементов по без повторений.

Число перестановок из элементов без повторений обозначается P_n от французского слова perturbation.

Теорема: число способов расположить в ряд различных объектов есть

$P_n = n(n - 1)(n - 2) \cdot \ldots \cdot 2 \cdot 1 = n!$

Замечание: Рекуррентная формула: $P_n = nP_{n - 1}$ .

Перестановки симметричных объектов

различных предметов можно расположить по кругу (n - 1)! способами, а если их можно еще и переворачивать, то $\frac{{(n - 1)!}}{2}$ различными способами.

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

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

Если из объектов выбирают штук, то число выборов последнего объекта есть n - k невыбранных объектов, что означает наличие n - k + 1 возможности выбора последнего выбранного объекта. То же, другими словами: после выбора первых k
- 1 элемента остается выбрать n - (k - 1) = n - k + 1 элемент.

Теорема: число размещений различных элементов по различным позициям есть

$A_{\,n}^{\,k} = n(n - 1)(n - 2) \ldots (n - k + 1)$ ,

или, в терминах факториалов,

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

Примечание: заметим, что в случае, когда число мест, по которым размещают предметы, совпадает с количеством самих предметов, т. е. когда k = n , рассматриваемая задача становится задачей о числе перестановок. В нашем случае при этом мы получаем в знаменателе дроби ноль факториал, и для того, что бы разные формулы, соответствующие одной и той же задаче, приводили к одинаковым результатам, полагают, что 0! = 1 .

Сочетания

Подсчитаем количество способов, которыми можно выбрать из различных предметов. Такие выборки называются сочетаниями, а их количество обозначается $C_n^{\,k}$ .

При k < n , выбрать k предметов из n можно $A_{\,n}^{\,k}$ способами, переставляя их P_k способами:

$C_n^{\,k} = \frac{{A_{\,n}^{\,k} }}{{P_k }} = \frac{{n!}}{{(n - k)!\,\, \cdot k!}}$ .

Рекуррентная формула: $C_m^n = C_m^{n - 1} \frac{{m - n + 1}}{n}$ .

Свойства сочетаний: $C_m^n = C_m^{m - n}$ ; $\;C_m^n + C_m^{n + 1} = C_{m + 1}^{n + 1}$ .

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

Пусть даны n_1 элементов первого типа, n_2 — второго типа, ..., n_k — -го типа, всего элементов. Способы разместить их по различным местам называются перестановками с повторениями. Их количество обозначается $P_n (n_1 ,\,\,n_2 ,\,\, \ldots ,\,\,n_k )$ .

Теорема: число перестановок с повторениями есть

$P_n (n_1 ,\,\,n_2 ,\,\, \ldots ,\,\,n_k ) = \frac{{n!}}{{n_1 !n_2 ! \ldots n_k !}}$ .

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

Пусть даны различных видов предметов, которые можно разместить по различным местам, причем выбирать предметы можно с повторениями (т.е. можно выбрать несколько предметов одного вида). Такие выборки называются размещениями с повторениями, а их количество вычисляется по формуле: $\bar A_{\,n}^{\,k} = n^k$ .

Сочетания с повторениями

Пусть имеются предметы различных видов предметов, и из них составляются наборы, содержащие элементов. Такие выборки называются сочетаниями с повторением. Их число обозначается $\bar C_n^{\,k}$ .

Теорема: число сочетаний с повторениями может быть вычислено по формулам:

$\bar C_n^{\,k} = C_{n + k - 1}^{\,k} = C_{n + k - 1}^{\,n - 1}$ .

Оставить комментарий

Сообщить об ошибке