1.3.5. Правило сложения и правило умножения комбинаций
Эти правила записаны в общем виде в Приложении Формулы Комбинаторики (пункт 4) и весьма напоминают алгебру событий:
1) Правило сложения комбинаций. Знак «плюс» следует понимать и читать как союз ИЛИ. Вспоминаем демонстрационную задачу с яблоком, грушей и бананом:
способами можно выбрать хотя бы один фрукт.
То есть, можно взять 1 фрукт (любой из трёх) ИЛИ какое-нибудь сочетание двух фруктов (любое) ИЛИ все три фрукта. Заметьте, что сложение комбинаций предполагает безразличие выбора (в данном случае без разницы – будет ли выбран 1, 2 или 3 фрукта).
Теперь рассмотрим более содержательный пример:
Задача 7
Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно выбрать 2 человек одного пола?
Решение: в данном случае подсчёт количества сочетаний 
, не годится – по той причине, множество комбинаций из двух человек включает в себя и разнополые пары.
Условие «выбрать 2 человек одного пола» подразумевает, что нужно выбрать двух юношей или двух девушек, и уже сама словесная формулировка указывает на верный путь решения:
способами можно выбрать 2 юношей;
способами можно выбрать 2 девушек.
Таким образом, двух человек одного пола (без разницы – юношей или девушек) можно выбрать: 
способами.
Ответ: 123
2) Правило умножения комбинаций. Знак «умножить» следует понимать и читать как союз И.
Рассмотрим ту же студенческую группу, которая пошла на танцы. Сколькими способами можно составить пару из юноши и девушки?
способами можно выбрать 1 юношу;
способами можно выбрать 1 девушку.
Таким образом, одного юношу и одну девушку можно выбрать:
способами.
Когда из каждого множества выбирается по одному объекту, то справедлив следующий принцип подсчёта комбинаций: «каждый объект из одного множества может составить пару с каждым объектом другого множества».
То есть, Олег может пригласить на танец любую из 13 девушек, Евгений – тоже любую из 13 девушек, и аналогичный выбор есть у остальных молодых людей. Итого:
возможных пар.
Следует отметить, что в данном примере не имеет значения упорядоченность пары, однако если принять во внимание инициативу, то количество комбинаций нужно удвоить, поскольку каждая из 13 девушек тоже может пригласить на танец каждого из 10 юношей. Всё зависит от условия той или иной задачи!
Этот же принцип справедлив и для более сложных комбинаций, например: сколькими способами можно выбрать 2 юношей и 2 девушек для участия в сценке КВН?
Союз И недвусмысленно намекает, что комбинации следует перемножить:
возможных групп артистов.
Иными словами, каждая пара юношей (45 уникальных пар) может выступить с каждой парой девушек (78 уникальных пар). А если рассмотреть распределение ролей между участниками, то комбинаций будет ещё больше. …Очень хочется, но всё-таки воздержусь от продолжения, чтобы не привить вам отвращение к студенческой жизни =).
Правило умножения комбинаций распространяется и на бОльшее количество множителей:
Задача 8
Сколько существует трёхзначных чисел, которые делятся на 5?
Решение: для наглядности обозначим данное число тремя звёздочками: ***
Комбинации будем считать по разрядам – слева направо:
В разряд тысяч можно записать любую из 
цифр (1, 2, 3, 4, 5, 6, 7, 8 или 9). Ноль не годится, так как в этом случае число перестаёт быть трёхзначным.
А вот в разряд десятков («посерединке») можно выбрать любую из 10 цифр: 
По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры.
Итого, существует:
трёхзначных чисел, которые делятся на 5.
При этом произведение 
расшифровывается так: «9 способами можно выбрать цифру в разряд сотен и 10 способами выбрать цифру в разряд десятков и 2 способами – в разряд единиц»
Или ещё проще: «каждая из 9 цифр в разряде сотен комбинируется с каждой из 10 цифр в разряде десятков и с каждой из двух цифр в разряде единиц».
Ответ: 180
…да, чуть не забыл об обещанном комментарии к Задаче 5, в которой Боре, Диме и Володе можно сдать по одной карте 
способами. Умножение здесь имеет тот же смысл: 
способами можно извлечь 3 карты из колоды И в каждой выборке переставить их 
способами.
А теперь задача для самостоятельного решения… сейчас придумаю что-нибудь поинтереснее, …пусть будет про ту же русскую версию Блэкджека:
Задача 9
Сколько существует выигрышных комбинаций из 2 карт при игре в «очко»?
Справка: выигрывает комбинация 10 + ТУЗ (11 очков) = 21 очко, и давайте будем считать выигрышной комбинацию из 2 тузов (порядок карт в любой паре не имеет значения).
Кстати, не надо считать пример примитивным. Блэкджек – это чуть ли не единственная игра, для которой существует математически обоснованный алгоритм, позволяющий систематически выигрывать у казино, и желающие могут найти массу информации об оптимальной стратегии и тактике. Правда, такие мастера довольно быстро попадают в чёрный список всех заведений 🙂
Полную и свежую версию этой книги в pdf-формате ,
а также курсы по другим темам можно найти здесь.
Также вы можете изучить эту тему подробнее – просто, доступно, весело и бесплатно!
С наилучшими пожеланиями, Александр Емелин
Источник
1.3.1. Перестановки, сочетания и размещения без повторений
Начнём с хвоста заголовка – что значит «без повторений»? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов, либо которые считаются таковыми по смыслу задачи.
Представьте, что перед вами на столе слева направо выложены:
яблоко / груша / банан
Вопрос первый: сколькими способами их можно переставить?
Одна комбинация уже записана выше и с остальными проблем не возникает:
яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко
Итого: 6 комбинаций или 6 перестановок.
Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт! Пожалуйста, откройте Приложение Основные формулы комбинаторики и в пункте № 2 найдите формулу количества перестановок. Никаких мучений – 3 объекта можно переставить: 
способами.
Вопрос второй: сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?
а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний (см. тот же п.2 Приложения): 
Запись 
следует читать и понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?».
б) Перечислим все возможные сочетания двух фруктов:
яблоко и груша;
яблоко и банан;
груша и банан.
Количество комбинаций легко проверить по той же формуле: 
Запись 
понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».
в) И, наконец, три фрукта можно выбрать единственным способом:
Следует отметить, что формула количества сочетаний сохраняет смысл и для пустой выборки:
способом можно выбрать ни одного фрукта – собственно, ничего не взять и всё. Но это явно не про студенток J
г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта (любые) или все 3 фрукта:
способами можно выбрать хотя бы один фрукт.
…внимательные читатели уже кое о чём догадались. Но о смысле знака «плюс» позже.
И для ответа на третий вопрос мне требуется два добровольца…, ну что же, раз никто не хочет, тогда буду вызывать к доске =)
Вопрос третий: сколькими способами можно раздать по одному фрукту Даше и Наташе?
Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно 
способами, перепишу их заново:
яблоко и груша;
яблоко и банан;
груша и банан.
Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей – Наташу;
либо наоборот – груша достанется Даше, а яблоко – Наташе.
И такая перестановка возможна для каждой пары фруктов.
В данном случае работает формула количества размещений: 
Она отличается от формулы 
тем, что учитывает не только количество способов, которым можно выбрать несколько объектов, но и все перестановки объектов в каждой возможной выборке. Так, в рассмотренном примере, важно не только то, что можно просто выбрать, например, грушу и банан, но и то, как они будут распределены (размещены) между Дашей и Наташей.
Пожалуйста, ещё раз внимательно перечитайте пункт № 2 Приложения Основные формулы комбинаторики и постарайтесь хорошо уяснить разницу между перестановками, сочетаниями и размещениями. В простых случаях легко пересчитать все возможные комбинации вручную, но чаще всего это становится трудноподъёмной задачей, именно поэтому и нужно понимать смысл формул.
Теперь остановимся на каждой комбинации подробнее:
Полную и свежую версию этой книги в pdf-формате ,
а также курсы по другим темам можно найти здесь.
Также вы можете изучить эту тему подробнее – просто, доступно, весело и бесплатно!
С наилучшими пожеланиями, Александр Емелин
Источник
