Правило множення
Правило множення (Основне правило комбінаторики)
Якщо потрібно виконати одну за одною дві дії, і першу з них можна виконати n способами, а другу, після виконання першої, m способами, тоді обидві ці дії (одну за одною) можна виконати m*n способами. Іншими словами: якщо в умові задачі використовується «І», то слід використовувати операцію множення. Ключові вираження у формулюванні, що призводять до правила множення: «і те, і інше», «одночасно», «незалежно», «кожен з».
Приклади
В цьому прикладі ми бачимо, що за правилом ми множимо 2 і 3 і отримуємо 6: 2*3=6.
Кількість способів вибору елемента з { A , B , C } є 3 × 3 = 9.
Простий
Вибрати книгу та диск з 10 книг і 12 дисків можна 10 * 12 = 120 способами.
І ще один приклад: коли Ви вирішите замовити піцу, вам необхідно спочатку вибрати тип тіста: тонке або товсте (2 варіанти). Далі ви обираєте одне можливе посипання: сир, пепероні або ковбаса (3 варіанти). За правилом множення, існує 2 * 3 = 6 можливих комбінацій замовлення піци.
Кількість розміщень з повтореннями
Якщо є множина з n типів елементів, і потрібно на кожному з m місць розташувати елемент якого-небудь типу (типи елементів можуть збігатися на різних місцях), то кількість варіантів цього буде nm.
Складений
Нехай потрібно знайти кількість слів, складених не більше, ніж з 3 літер алфавіту { a, b, c, d }. Кількість n-літерних слів дорівнює кількості розміщень з 4 літер на n місць з повтореннями — воно дорівнює 4n. Кількість всіх слів буде складатися з кількостей одно-, дво- і трибуквених слів. Тоді відповідь на початкове питання буде 41 + 42 + 43 = 84.
Застосування
В теорія множин, цей принцип множення часто визначається як добуток кардинальних чисел. Ми отримуємо
де х це декартів добуток множин.