Как пользоваться правилом умножения в комбинаторике?
Слышал про «правило умножения» в комбинаторике, но не понимаю, когда его применять. Как посчитать число вариантов, например, для составления пароля или меню?
2 ответа
Правило умножения (основной принцип комбинаторики): если первый выбор можно сделать a способами, а второй — b способами, то вместе их можно сделать a · b способами. Для нескольких шагов — перемножаем все.
Пример (меню). В кафе 3 первых блюда, 4 вторых, 2 напитка. Сколько вариантов обеда?
3 · 4 · 2 = 24 варианта.
Пример (номера). Сколько 3-значных чисел можно составить из цифр 1–9, если цифры могут повторяться?
На каждой из 3 позиций — 9 вариантов: 9 · 9 · 9 = 729.
Пример (пароль без повторов). Сколько 4-буквенных «слов» из 26 букв, если буквы не повторяются?
Первая буква — 26 вариантов, вторая — 25 (одна занята), третья — 24, четвёртая — 23:
26 · 25 · 24 · 23 = 358 800. Это, кстати, и есть размещения A(26,4).
Когда применять: если задачу можно разбить на последовательные независимые шаги выбора, перемножай число вариантов на каждом шаге. Главное — следить, меняется ли число вариантов после каждого шага (повторы разрешены или нет).
Связь с другими формулами: правило умножения — фундамент всей комбинаторики. Из него выводятся и n! (перестановки), и размещения A(n,k). Просто запомни логику «шаг за шагом перемножаем варианты», и большинство задач решается без зубрёжки формул. Не путай с правилом сложения — оно для «или» (выбор из непересекающихся групп).