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

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

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

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

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

В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 способами.

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

Определение. Перестановкой 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) повторения цифр разрешены.

Решение.

Рассмотрим первый набор чисел.

Если повторения запрещены, то каждое число – размещение из соответствующего количества цифр, следовательно, количество разных трех-, четырех-, пятизначных чисел равно

= .

Если повторения разрешены, воспользуемся принципом умножения, каждое действие (задание очередной цифры) можно выполнить пятью способами.

Трехзначных чисел всего 5 × 5 × 5 = 125; четырехзначных чисел всего 5 × 5 × 5 ×5 = 625; пятизначных чисел всего 5 × 5 × 5 × 5× 5 = 3125.

Итого 3875 разных чисел.

Рассмотрим второй набор чисел.

Ноль не может стоять первой цифрой в числе, поэтому, если повторения запрещены, то разных трехзначных чисел всего 4 × 4 × 3 = 48;

разных четырехзначных чисел – 4 × 4 × 3 × 2 = 96; разных пятизначных чисел – 4 × 4 × 3 × 2 × 1 = 96. Всего 240 чисел.

Если повторения разрешены, трехзначных чисел всего 4 × 5 × 5 = =100; четырехзначных чисел  4 × 5 × 5 × 5 = 500; пятизначных чисел  4 ×

 5 × 5 × 5 × 5 = 2500. Всего 3100 чисел.

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

В неупорядоченном наборе порядок перечисления элементов не важен.

Пример 1. Из букв A, B, C, D, E можно составить 10 разных сочетаний по три буквы: {A,B,C}; {A,B,D}; {A,B,E}; {A,C,D}; {A,C,E}; {A,D,E}; {B,C,D}; {B,C,E}; {B,D,E}; {C,D,E}.

Подчеркнем, что сочетание {A, B ,C} тождественно сочетанию {B, C, А}. Но перестановки АВС и ВСА – различны.

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

Любому неупорядоченному набору (сочетанию), содержащему k разных элементов, можно поставить в соответствие k упорядоченных наборов (перестановок) этих элементов.

Таким образом,

= (3)

Числа называются биномиальными коэффициентами.

Некоторые свойства биномиальных коэффициентов

= = 1.	= = 1.
= = n.	= = .
= = .
= + = = = = = .

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

Решение. Варианты распределения людей по комнатам таковы.

Вариант 1: в первой комнате – 3 человека; во второй – 5 человек.

Вариант 2: в первой комнате – 4 человека; во второй – 4 человека.

Вариант 3: в первой комнате – 5 человек; во второй – 3 человека.

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

Выбрать трех человек для первой комнаты можно n₁ = = = 56 способами. Выбрать четырех человек для первой комнаты можно n₂ = = = 70 способами. Выбрать пять человек для первой комнаты можно n₃ = = = = 56 способами. Число всех способов разместить людей равно n₁ + n₂ + n₃= 56 + 70 + 56 = 182.

Пример 3.

Сколько всего существует различных последовательностей, состоящих из нулей и единиц, в каждой из которых m нулей и n единиц.

Решение. Чтобы задать такую последовательность, надо выполнить одно действие – выбрать из (n + m) позиций для цифр m позиций для нулей (n позиций для единиц). Число способов выполнить это действие равно .

Например, если m = 2, n = 3, то =10. Эти последовательности таковы: 01101, 00111, 10011, 11100, 10101 и т.д.