Материал: Лекции 1-2.docx

от выбора элемента A) k способами, то пару элементов A и B (в указанном порядке) можно выбрать m·k способами.

Для любого конечного числа элементов правило произведения можно сформулировать в общем виде. Пусть требуется выполнить одно за другим k

действий. Если первое действие можно выполнить n1 способами, второе действие –n2 способами, третье –n3 способами и так до k -го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены n1 · n2 ·...· nk способами. Это правило называется основным законом комбинаторики.

Примеры:

1. Сколько существует двузначных чисел?

►В двузначном числе количество десятков может быть обозначено любой цифрой от 1 до 9, а единиц от 0 до 9. Таким образом, существует 10

двузначных чисел вида 1 , десять чисел вида 2 и т.д. Следовательно, всего двузначных чисел 9∙ 10 = 90.◄

2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

►Представим пятизначное число одинаково читающееся слева направо и справа налево в виде XYZYX, где X не может быть равно нулю, а Y и Z -

любые. Итак, по правилу произведения, количество цифр, одинаково читающихся как слева направо, так и справа налево равно 9∙ 10 ∙ 10 = 900.◄ 3. В чемпионате Республики по шахматам принимает участие 16

человек. Сколькими способами могут быть распределены золотая и серебряная медали?

► Золотую медаль может получить один из 16 шахматистов. После получения золотой медали, серебряную медаль может иметь один из 15-ти оставшихся участников. Таким образом, общее количество способов,

которыми могут быть распределены золотая и серебряная медали, равно 16 ·15

= 240. ◄

4. Пароль представляет собой последовательный набор одной буквы из

30 и двух цифр от 0 до 9. Какова вероятность набрать пароль правильно

(событие А) при одном случайном наборе буквы и двух цифр?

►При наборе пароля выбирается одна буква из 30: 1 = 30 и две цифры из 10 каждая: 2 = 10, 3 = 10, т.е. три совместные операции. Тогда число

Рассмотрим наиболее часто встречающиеся виды комбинаций:

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

Перестановки

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

число элементов множества.

Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком.

Перестановкой из n элементов называется набор из n элементов,

расположенных в определенном порядке.

Пример. Перестановки множества A = {a, b, c} из трех элементов имеют следующий вид: abc, acb, bac, bca, cab, cba.

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

элементов, на первое место можно поставить любой из данных n элементов,

на второе – любой из оставшихся (n-1) элементов и т.д. Таким образом, число всех перестановок из n элементов равно

Примеры:

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

►Каждое число будет некоторой перестановкой исходных цифр. Тогда число различных чисел равно числу перестановок 4!=24. ◄

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

►Шахматная доска имеет размер 8x8. Ладья бьет любую фигуру,

находящуюся с ней в одной строке, или в одном столбце шахматной доски.

Чтобы ладьи не били друг друга, их нужно разместить в различных столбцах и строках. Пусть первая ладья стоит в первом столбце, вторая – во втором и т.д. Тогда выбор строк для ладей будет являться перестановкой из восьми элементов, т.е. число расстановок ладей равно 8!=40320. ◄

Размещения

Пусть имеется множество, содержащее n элементов. Каждое его упорядоченное подмножество, состоящее из k элементов, называется

размещением из n элементов по k элементов (размещением из n по k).

Очевидно, что 0 ≤ k ≤ n и размещения из n по k – это все k - элементные подмножества (n - элементного множества), отличающиеся составом

элементов или порядком их следования.

Примеры:

1. Сколькими способами можно рассадить 3-х студентов на 22-х местах? ►Рассадка студентов будет отличаться порядком, следовательно используем подсчет числа размещений (3): 322 = (2222!−3)! = 22 ∙ 21 ∙ 20 =

9240. ◄

2. Три оператора сотовой связи могут работать на одном из четырех частотных диапазонов. Какова вероятность того, что при одновременном и независимом сеансе связи (событие С) они будут работать на разных частотах?

► Число, благоприятствующее исходу события С: = 34 = 4!1! = 24. А

так как операторы выбирают частотный диапазон независимо, то по правилу произведения = 4 ∙ 4 ∙ 4 = 64. Тогда искомая вероятность равна ( ) = =

2464 = 38 = 0,375. ◄

Сочетания

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

Число всех сочетаний из n по k обозначается и вычисляется:

Примеры:

1. Кодовый замок устроен так, что порядок набираемых цифр не важен, а

каждую цифру можно использовать только один раз. Сколько различных четырехзначных кодов поддерживает этот замок?

►Так как порядок набираемых цифр не важен, для вычисления числа кодов используем формулу (4):

2. У одного филателиста 8 марок, а у второго – 11. Сколькими способами они могут обменять друг у друга две марки на две?

► Так как надо порядок следования марок не имеет значения, то выбор двух марок - сочетание. Первый филателист может выбрать две марки из восьми 82 способами. Второй может выбрать две марки из одиннадцати