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

Определение (вариант 1). В комбинаторике размещением (из \(n\) по \(k\)) называется упорядоченный набор из \(k\) различных элементов из некоторого множества различных \(n\) элементов.

Определение (вариант 2). Размещениями множества из \(n\) различных элементов по m элементов (\(m \leq n\)) называются комбинации, которые составлены из данных \(n\) элементов по \(m\) элементов и отличаются либо самими элементами, либо порядком элементов.

Число всех размещений множества из \(n\) элементов по \(m\) элементов обозначается через \(A_m^n\) (от начальной буквы французского слова "arrangement", что означает размещение), где \(n=1,2,...\) и \(m=\overline{1,n}\).

Теорема. Число размещений множества из \(n\) элементов по \(m\) элементов равно

\[A_n^m=n(n-1)\dots(n-m+1).\]

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

Определение (вариант 1). Перестановкой множества из \(n\) элементов называется расположение этих элементов в определенном порядке.

Определение (вариант 2). В комбинаторике перестановка — это упорядоченный набор без повторений элементов \(a_1, a_2, ..., a_n\).

Перестановки можно считать частным случаем размещений при \(m = n\).

Число всех перестановок из \(n\) элементов обозначается \(P_n\) (от начальной буквы французского слова "permutation", что значит "перестановка").

Число всех различных перестановок вычисляется по формуле
\[P_n =n(n-1) \cdot \ldots \cdot 2 \cdot 1= n!. \]

Сочетание без повторений

Определение. Сочетаниями из \(n\) различных элементов по \(k\) элементов называются комбинации, которые составлены из данных \(n\) элементов по \(k\) элементов и отличаются хотя бы одним элементом (иначе говоря, \(k\)-элементные подмножества данного множества из \(n\) элементов).

Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из \(n\) элементов по \(k\) элементов в каждом обозначается \(C_n^k\) (от начальной буквы французского слова "combinasion", что значит "сочетание").

Теорема.

\[C_n^k = \frac{n!}{k!(n-k)!} \qquad (0\le k \le n).\]

Бином Ньютона:

\[(a + b)^n = \sum\limits_{k=0}^n C_n^k a^{n-k}b^k.\]

Треугольник Паскаля:

\[\newcommand\cn[3]{\llap{#1}#2\rlap{#3}} \begin{array}{c} &&&&&&\cn{}{1}{}\\ &&&&&\cn{}{1}{}&&\cn{}{1}{}\\ &&&&\cn{}{1}{}&&\cn{}{2}{}&&\cn{}{1}{}\\ &&&\cn{}{1}{}&&\cn{}{3}{}&&\cn{}{3}{}&&\cn{}{1}{}\\ &&\cn{}{1}{}&&\cn{}{4}{}&&\cn{}{6}{}&&\cn{}{4}{}&&\cn{}{1}{}\\ &\cn{}{1}{}&&\cn{}{5}{}&&\cn{1}{}{0}&&\cn{1}{}{0}&&\cn{}{5}{}&&\cn{}{1}{}\\ \cn{}{1}{}&&\cn{}{6}{}&&\cn{1}{}{5}&&\cn{2}{}{0}&&\cn{1}{}{5}&&\cn{}{6}{}&&\cn{}{1}{} \end{array} \\ \ldots \quad \ldots \quad \ldots\]

или

\[\newcommand\cn[3]{\llap{#1}#2\rlap{#3}} \begin{array}{c} &&&&&&\cn{}{C_0^0}{}\\ &&&&&\cn{}{C_1^0}{}&&\cn{}{C_1^1}{}\\ &&&&\cn{}{C_2^0}{}&&\cn{}{C_2^1}{}&&\cn{}{C_2^2}{}\\ &&&\cn{}{C_3^0}{}&&\cn{}{C_3^1}{}&&\cn{}{C_3^2}{}&&\cn{}{C_3^3}{}\\ &&\cn{}{C_4^0}{}&&\cn{}{C_4^1}{}&&\cn{}{C_4^2}{}&&\cn{}{C_4^3}{}&&\cn{}{C_4^4}{}\\ &\cn{}{C_5^0}{}&&\cn{}{C_5^1}{}&&\cn{}{C_5^2}{}&&\cn{}{C_5^3}{}&&\cn{}{C_5^4}{}&&\cn{}{C_5^5}{}\\ \cn{}{C_6^0}{}&&\cn{}{C_6^1}{}&&\cn{}{C_6^2}{}&&\cn{}{C_6^3}{}&&\cn{}{C_6^4}{}&&\cn{}{C_6^5}{}&&\cn{}{C_6^6}{} \end{array} \\ \ldots \quad \ldots \quad \ldots\]

• Вперёд >