Основные комбинаторные конструкции: перестановки, размещения, сочетания

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

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

Если среди элементов нет одинаковых, то число перестановок из n элементов обозначают символом P_n («пэ из эн») и вычисляют по формуле:

P_n = 1 · 2 · 3 · … · (n - 2) · (n - 1) · n.

Для произведения первых n натуральных чисел есть специальное обозначение n! («эн факториал»). При этом 0! принимается за единицу, то есть 0! = 1.

Пример 1. 5! = 1×2×3×4×5 = 120.

Пример 2. Сколькими способами можно расставить 6 бегунов и 6 беговых дорожках?

Число способов, очевидно, равно числу перестановок из 6 элементов:

P ₆ = 1 · 2 · 3 · 4 · 5 · 6 = 720.

Если среди n элементов есть повторяющиеся, то число перестановок из n элементов обозначают символом P_n (n₁, n₂, …, n_s) (перестановки с повторениями) и вычисляют по формуле:

Здесь n₁, n₂, …, n_s – количество одинаковых элементов по группам.

Определение. Размещением из n элементов по k (k £ n) называется любое множество, состоящее из любых k элементов, взятых в определённом порядке из данных n элементов.

Если один и тот же элемент нельзя брать более одного раза, то число размещений из n элементов по k обозначают («а из эн по ка») и вычисляют по формуле:

= n · (n - 1) · (n - 2) · … · (n – k + 1).

Заметим, что = n · (n - 1) · (n - 2) · … · (n - (n - 1)) = n · (n - 1) · … · 2 · 1 = P_n.

 

Пример. Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нём было 4 различных предмета?

Любое расписание на один день, составленное из 4 различных предметов, отличается от другого либо самыми предметами, либо порядком их следования, то есть важен и порядок, и сами элементы, - это размещения: = 8 · 7 · 6 · 5 = 1680.

Если один и тот же элемент можно использовать более одного раза, то число размещений из n элементов по k обозначают (размещение с повторениями) и вычисляют по формуле: . Здесь s – количество различных элементов среди n элементов.

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

Если среди данных n элементов нет одинаковых, то число сочетаний из n элементов по k обозначают («цэ из эн по ка») и вычисляют по формуле:

Заметим, что связь между сочетаниями, размещениями и перестановками выражается формулой

или .

Пример. Из 12 членов группы надо выбрать трёх для поездки в магазин. Сколькими способами это можно сделать?

Очевидно, что здесь важны только сами элементы (конкретные люди), следовательно, это сочетания: .

Если среди n элементов есть повторяющиеся, то число сочетанийобозначают (сочетания с повторениями) и вычисляют по формуле: . Здесь s – количество различных элементов среди n элементов.

Основные формулы

Если один и тот же элемент можно использовать более одного раза, то число размещений из n элементов по k обозначают (размещение с повторениями) и вычисляют по формуле: . Здесь s – количество различных элементов среди n элементов.

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

Если среди данных n элементов нет одинаковых, то число сочетаний из n элементов по k обозначают («цэ из эн по ка») и вычисляют по формуле:

Заметим, что связь между сочетаниями, размещениями и перестановками выражается формулой

или .

Пример. Из 12 членов группы надо выбрать трёх для поездки в магазин. Сколькими способами это можно сделать?

Очевидно, что здесь важны только сами элементы (конкретные люди), следовательно, это сочетания: .

Если среди n элементов есть повторяющиеся, то число сочетанийобозначают (сочетания с повторениями) и вычисляют по формуле: . Здесь s – количество различных элементов среди n элементов.