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

Комбинаторика, факториал, перестановка, размещение, сочетание [11:42]

001. Основы перечислительной комбинаторики — А. М. Райгородский // Компьютерные науки [2:12:08]

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

Определения

Установленный в конечном множестве порядок расположения его элементов называется перестановкой.

Произвольные неупорядоченные подмножества данного конечного множества называются сочетаниями.

Упорядоченные подмножества данного конечного множества называются размещениями.

Произвольные неупорядоченные суммы натуральных слагаемых, равные самому числу, называются разбиениями.

Назовём распределениями числа — упорядоченные суммы с фиксированным количеством слагаемых (включая нулевые), равные самому числу.

Основные формулы без повторений

Введём обозначения:

n – число элементов конечного множества;

m – число элементов подмножества конечного множества из n элементов;

P_n – число перестановок из n элементов;

C^m_n – число сочетаний из n элементов по m элементов;

A^m_n – число размещений из n элементов по m элементов.

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P_n = n! \Leftrightarrow P_n = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (n-1) \cdot n}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle C_n^m = \frac{n!}{m!(n-m)!} \Leftrightarrow C_n^m = \frac{n \cdot (n-1)\cdot \ldots \cdot(n-m+1)}{m!}}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle A_n^m = \frac{n!}{(n-m)!} \Leftrightarrow A_n^m = n \cdot (n-1)\cdot \ldots \cdot(n-m+1)}

Основные формулы с повторениями

Введём обозначения:

r — число видов (повторяющихся) элементов множества;

n — число элементов конечного множества, равное (сумме) n₁ + n₂ + … + n_r;

m — число элементов подмножества конечного множества;

P_{n, n1,n2,…,nr} — число перестановок из n элементов с n₁ повторениями элементов 1-го вида, с n₂ повторениями элементов 2-го вида, …, с n_r повторениями элементов r-го вида.

C^m_{n, m} — число сочетаний из n элементов по m элементов с возможными m повторениями;

A^m_{n, m} — число размещений из n элементов по m элементов с возможными m повторениями.

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P_{n,n_1,n_2\ldots,n_r}=\frac{n!}{n_1!\cdot n_2! \cdot \ldots \cdot n_r!} \Leftrightarrow P_{n,n_1,n_2\ldots,n_r}=\frac{(n_1+n_2+ \ldots +n_r)!}{n_1!\cdot n_2! \cdot \ldots \cdot n_r!}}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle C_{n,m}^m=\frac{(n+m-1)!}{m! \cdot (n-1)!}}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle A_{n,m}^m=n^m}

Основные операции

Составление перестановок — это образование упорядоченных множеств, состоящее в установлении определённого порядка следования элементов множества друг за другом.

Составление сочетаний — это образование подмножеств, состоящее в выделении из данного множества некоторой части его элементов.

Составление размещений — это образование упорядоченных подмножеств, содержащих фиксированное число элементов исходного множества.

Составление разбиений — это разложение натурального числа на натуральные слагаемые, сумма которых равна самому числу.

Составление распределений — это разложение натурального числа на фиксированное число элементов (слагаемых, включая нулевые), сумма которых равна самому числу.

Составление перестановок с повторениями — это образование упорядоченных множеств, состоящее в установлении определённого порядка следования элементов множества друг за другом с учётом их повторений.

Составление сочетаний с повторениями — это образование подмножеств, содержащих фиксированное число элементов исходного множества с учётом их повторений.

Составление размещений с повторениями — это образование упорядоченных подмножеств, содержащих фиксированное число элементов исходного множества с учётом их повторений.

Литература

• Халамайзер А. Я. Комбинаторика и бином Ньютона — М.: «Просвещение», 1980.