§ 17. Основные правила комбинаторики

Сколькими способами ученики класса могут выстроиться в очередь в буфет? Сколькими способами в классе выбирают старосту и заместителя старосты? Сколькими способами золото, серебро и бронза чемпионата достаются трём разным командам? Во всех этих вопросах надо сосчитать, сколько наборов, составленных по заданному правилу, получается из элементов конечного множества. Раздел математики, который отвечает на такие вопросы, называют комбинаторикой. Почти любую комбинаторную задачу разбирают с помощью двух правил — правила суммы и правила произведения.

Пусть путешественнику приглянулись 4 маршрута по Карелии и 6 маршрутов по Алтаю, а отпуска хватает только на один поход. Всего разных маршрутов 4 + 6 = 10, поэтому и выбрать поход он может 10 способами (рис. 1). Обрати внимание: ни один маршрут не попал в оба списка сразу.

Правило суммы. Если в множестве A ровно m элементов, в множестве B ровно k элементов, а общих элементов у этих множеств нет, то один элемент, взятый из A или из B, можно выбрать m + k способами.

Правило переносится на любое число множеств. Добавим третье множество C из n элементов, тоже без общих элементов с первыми двумя: тогда один элемент, взятый из A, из B или из C, выбирают m + k + n способами. Например, при 4, 6 и 5 маршрутах вариантов 4 + 6 + 5 = 15.

Вернёмся к путешественнику, но теперь отпуска хватает на два похода: сначала Карелия, потом Алтай. К каждому из 4 карельских маршрутов в пару годится любой из 6 алтайских, поэтому пар получается 6 + 6 + 6 + 6 = 6 · 4 = 24.