§3. Основные комбинаторные задачи.

1. Правило суммы.

Если имеется k способов выбрать элемент a и l способов

выбрать элемент b, то выбор элемента a либо b можно осуществить (k+l) способами. Если встречаются повторяющиеся элементы, то (k+l-n) способами, где n -число совпадающих элементов.

II. Правило произведения:

Если имеется k способов выбрать элемент a и l способов

выбрать элемент b, то выбор пары элементов (a;b)

(т.е. a и b) можно осуществить (k l) способами.

Пример: Из города А в город В ведут 5 дорог, а из города В в город С – 3 дороги. Сколько путей, проходящих через В ведут из города А го­род С?

Решение: По правилу произведения (АВ;ВС)=5 3=15.

III. Сочетания.

Пусть дано конечное множество Х={а₁,а₂ , ... , а_n}.

Определение: Сочетанием из n элементов, взятых по k, , называется часть, содержащая k элементов данного множества X, состоящего из n элементов, причём порядок элементов не учитывается.

Пример: Х={1,2,3,4}, n =4, k=2.

Это множества: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}. Всего 6 множеств.

Теорема: Число сочетаний , где , вычисляется по формуле:

Пример: = 6

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

Определение: Всякое конечное упорядоченное множество называется

переста­новкой его элементов.

Пример: Х= {1,2,3.}

Возможные перестановки образуют множества: {1,2,3}, {2,1,3}, {1,3,2}, {3,2,1},{3,1,2}, {2,З,1}. Всего шесть множеств.

Теорема: Число всевозможных перестановок вычисляется по формуле:

У. Размещения.

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

Пример: Х={1,2,3,4}, n =4, k=2.

Это множества: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4},{2,1}, {3,1}, {4,1}, {3,2}, {4,2}, {4,3} Всего 12 множеств.

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

Пример: Сколькими способами можно выбрать четырёхзначное число, все цифры которого различны?

Решение:

1-ю цифру четырёхзначного числа можно выбрать 9-ю способами /любую из цифр 1,2,3,4,5,6,7,8,9./ Цифру 0 брать нельзя, так как тогда число будет не четырёхзначное.

2-ю цифру можно выбрать также 9-ю способами. Теперь уже можно брать цифру 0, но первую выбранную цифру повторить нельзя.

3-ю цифру можно выбрать 8-ю способами. Уже первые две выбранные цифры повторить нельзя.

4-ю цифру можно выбрать 7-ю способами

Согласно правилу произведения, искомое число способов выбора четырёхзначного числа с различными цифрами равно: 9 9 8 7 = 4536.