1 вопрос. Размещения.

2 вопрос. Сочетания.

3 вопрос. Правила комбинаторики.

1 вопрос. Размещения.

Пусть имеются четыре буквы А, В, С, D. Составив все комби­нации только из двух букв, получим:

АВ, AC, AD;

ВА, ВС, BD;

СА, СВ, CD;

DA, DB, DC.

Мы видим, что все полученные комбинации отличаются или буквами, или их порядком (комбинации ВА и АВ считаются раз­личными).

Комбинации из n элементов по т элементов, которые отли­чаются друг от друга или самими элементами или порядком эле­ментов, называются размещениями.

Размещения обозначаются символом Aⁿ_m, где n — число всех имеющихся элементов, m — число элементов в каждой комбина­ции. При этом полагают, что т≤ п.

Число размещений можно вычислить по формуле

(1.3)

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

или по другой формуле (в факториальной форме)

. (1.4)

Так, A²₄ = 4· 3 = 12, что совпадает с результатом приведен­ного примера: поскольку число строк соответствует числу всех имеющихся букв, т.е. n = 4, а число столбцов равно 3, всего имеется 12 различных комбинаций.

1. Вычислить:

2. Сколько двузначных чисел можно составить из пяти цифр 1, 2, 3, 4, 5 при условии, что ни одна из них не повторяется?

Решение.

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

.

3. Расписание одного дня состоит из 5 уроков. Определить число вариантов расписания при выборе из 11 дисциплин.

Решение.

Каждый вариант расписания представляет набор 5 дисциплин из 11, отличающийся от других вариантов, как составом дисциплин, так и порядком их следования (или и тем и другим), т.е. является размещением из 11 элементов по 5. Число вариантов расписаний находим по формуле (3).

.

2 вопрос. Сочетания.

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

Так, из четырех различных букв А, В, С, D можно составить следующие комбинации, отличающиеся друг от друга хотя бы одним элементом: АВ, AC, AD, ВС, BD, CD. Значит, число соче­таний из четырех элементов по два равно 6. Это кратко записы­вается так: C ²₄ = 6.

В каждой комбинации сделаем перестановки элементов:

АВ, AC, AD, ВС, BD, CD,

ВА, СА, DA, CB, DB, DC.

В результате мы получили размещения из четырех элементов по два. Следовательно,

, откуда .

Следовательно, в общем случае число из п элементов по т равно числу раз­мещений из п элементов по т, деленному на число перестановок из т элементов:

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

. (1.5)

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

. (1.6)

4. Вычислить:

.

Отметим основные свойства числа сочетаний:

, (1.7)

. (1.8)

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

5. Сколькими способами можно выбрать трех дежурных, если в классе 30 учащихся?

.

6. В шахматном турнире участвуют 16 человек. Сколько партий должно быть сыграно в турнире, если между любыми двумя участниками должна быть сыграна одна партия?

Решение.

Каждая партия играется двумя участниками из 16 и отличается от других только составом пар участников, т.е. представляет собой сочетание из 16 элементов по 2. Их число находим по формуле (6):

.

3 вопрос. Правила комбинаторики.

Пусть A_i (i=1, 2, … n) – элементы конечного множества.

При решении задач комбинаторики используют следующие правила.

Правило суммы. Если элемент A₁ может быть выбран n₁ способами, элемент A₂ – другими n₂ способами, A₃ - отличными от первых двух n₃ способами и т.д., A_k - n_k способами, отличными от первых (k-1), то выбор одного из элементов: или A₁, или A₂, … или A_k может быть осуществлен n₁ + n₂ + ...+ n_k способами.

7. В ящике 300 деталей. Известно, что 150 из них – 1-го сорта. 120 – 2-го, а остальные – 3-го сорта. Сколько существует способов извлечения из ящика одной детали 1-го или 2-го сорта?

Решение.

Деталь 1-го сорта может быть извлечена n₁ = 150 способами, 2-го - n₂ = 120 способами. По правилу суммы существует n_{1 +} n₂ = 150 + 120 = 270 способов извлечения одной детали 1-го или 2-го сорта.

Правило произведения. Если элемент A₁ может быть выбран n₁ способами, после каждого такого выбора элемент A₂ может быть выбран n₂ способами и т.д., после каждого (k-1) выбора элемент A_k может быть выбран n_k способами, то выбор всех элементов A₁, A₂, … или A_k в указанном порядке может быть осуществлен n₁·n₂·...n_k способами.

8. В группе 30 человек. Необходимо выбрать старосту, его заместителя и профорга. Сколько существует способов это сделать?

Решение.

Староста может быть выбран любой из 30 учащихся, его заместителем – любой из оставшихся 29, а профоргом - любой из оставшихся 28 учащихся, т.е. n₁ = 30, n₂ = 29, n₃ = 28. По правилу произведения общее число способов выбора старосты, его заместителя и профорга равно n₁·n₂·n₃ = 30 · 29 · 28 = 24360 способов.