В2.2. Перестановки, размещения, сочетания

В2.1. Принцип умножения

Краткое содержание лекции

· Принцип умножения

· Перестановки, размещения, сочетания

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

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

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

Основным в элементарной комбинаторике является принцип умножения.

Принцип умножения.

Пусть требуется выполнить одно за другим n действий, причем 1-е действие можно выполнить k₁ способами; 2-е – k₂ способами; 3-е – k₃ способами;…; n-е - k_n способами. И число способов, которыми можно выполнить каждое действие, не зависит от того, какие способы были выбраны для выполнения предшествующих действий. Тогда число способов, которыми можно выполнить все n действий, равно произведению k₁ × k₂ × k₃ × ... × k_n. Это и есть принцип умножения. Проще всего объяснить справедливость принципа умножения можно при помощи диаграммы (рис. 2).

Пример.

У человека имеется 3 рубашки (Р_1, Р_2, Р₃), 2 галстука (Г₁, Г₂) и 2 пары ботинок (Б₁, Б₂). Он признает любое сочетание этих элементов. Сколькими способами он может одеться?

Решение.

Чтобы одеться, человек должен выполнить одно за другим и независимо одно от другого 3 действия:

1. Выбрать рубашку (три способа).

2. Выбрать галстук (два способа).

3. Выбрать ботинки (два способа).

Все способы выбора костюма показаны на диаграмме (рис. 2).

Рис. 2

Всего можно одеться 3 × 2 × 2 = 12 способами.

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

Пример 1.

Из трех элементов A,B,C можно составить шесть разных перестановок: ABC; ACB; CAB; CBA; BAC; BCA.

Число различных перестановок п элементов обозначается Р_п. Выведем формулу подсчета числа Р_п, для чего воспользуемся принципом умножения.

Чтобы определить перестановку n данных различных элементов, нужно выполнить одно за другим n действий:

· выбрать первый элемент перестановки (n способов);

· указать второй элемент (n - 1 способ);

…………………………………………;

· назвать последний элемент перестановки (1 способ).

Эти действия выполняются независимо одно от другого. В силу принципа умножения

P_n = n × (n - 1) ×...× 1 = n! (1)

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

Пример 1.

Из букв A, B, C, D можно составить 12 размещений из двух букв:

AB; BA; AC; CA; AD; DA; BC; CB; BD; DB; CD; DC.

Число различных размещений обозначается символом . Выведем формулу его подсчета.

Чтобы составить размещение, нужно выполнить одно за другим и независимо одно от других k действий:

· назвать первый элемент размещения (n способов);

· указать второй элемент (n - 1 способ);

……………………………………………;

· назвать k-й, последний, элемент (n – k + 1 способов).

В соответствии с принципом умножения

= n × (n – 1) ×...× (n – k + 1) =

= (2)

Пример 2. Сколько трех-, четырех-, пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5 (0, 1, 2, 3, 4), если

a) повторения цифр запрещены;

b) повторения цифр разрешены.

Решение.