Задачи. 
Комбинаторика. 
История создания теории

Все задания взяты с пособия И. В. Яковлева «Комбинаторика — олимпиаднику».

Правило суммы Задача 1. На подносе лежат 5 яблок и 3 груши. Сколькими способами можно выбрать фрукт с подноса?

Решение: Яблоко можно выбрать пятью способами. Грушу — тремя. Стало быть, один из этих фруктов можно выбрать 5 + 3 = 8 способами.

Задача 2. На полке стоит 10 томов Пушкина, 4 тома Лермонтова и 6 томов Гоголя. Сколькими способами можно выбрать с полки 1 книгу?

Решение: 10 + 4 + 6 = 20 способами.

Правило произведения Задача 3. В магазине есть 7 видов пиджаков, 5 видов брюк и 4 вида галстука. Сколькими способами можно купить комплект из пиджака, брюк и галстука?

Решение: Предположим, что пиджак уже выбран (это можно сделать 7 способами). К пиджаку выбираем брюки 5 способами. Итого пару (пиджак, брюки) можно выбрать 7×5 способами. К этой паре можно купить галстук 4 способами. Следовательно, для покупки пиджака, брюк и галстука имеется.

7 х 5×4 = 140 способов.

Задача 4. Сколько подмножеств у 5-элементного множества? У n-элементного?

Решение: Пусть имеется множество из 5 элементов A = {a₁, a_2,a₃, a₄, a₅}. Каждому его подмножеству B можно дать уникальное имя в виде в виде упорядоченной пятёрки нулей и единиц по следующему правилу: если на i-й позиции стоит единица, то a_i? B; если же на i-й позиции пятёрки стоит нуль, то a_i? B.

Например, пятёрка 10 010 обозначает подмножество {a₁, a₄,}. Пятёрки 0 и 11 111 обозначают соответственно пустое множество и само множество A.

Таким образом, у множества A имеется ровно столько подмножеств, сколько существует упорядоченных пятёрок из нулей и единиц. Каждую позицию пятёрки можно заполнить двумя способами (0 или 1), поэтому таких пятёрок 2×2×2×2×2 = 2⁵ = 32. Это и есть число подмножеств 5-элементного множества.

Для n-элементного множества рассуждение аналогично. Каждое его подмножество получает уникальное имя (по тому же правилу) в виде цепочки длины n, состоящей из нулей и единиц. Всего таких цепочек 2ⁿ. Следовательно, число всех подмножеств n-элементного множества равно 2ⁿ.

Размещения с повторениями Задача 5. Сколькими способами можно m различных шаров в n различных ящиков? На число шаров в ящике ограничений нет.

Решение: Представим себе m клеток (это шары). В каждую клетку можно вписать любое число от 1 до n (номер ящика, в который кладётся шар). Всего получится n^m всевозможных способов заполнить клетки, то есть разложить шары по ящикам.

Число разложений m различных шаров по n различным ящикам (без ограничений шаров в ящике) называется иногда числом размещений с повторениями из n по m и обозначается, и это обозначение равно n^m.