Правило множення

Правило множення (Основне правило комбінаторики)

Якщо потрібно виконати одну за одною дві дії, і першу з них можна виконати 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 місць розташувати елемент якого-небудь типу (типи елементів можуть збігатися на різних місцях), то кількість варіантів цього буде n^m.

Складений

Нехай потрібно знайти кількість слів, складених не більше, ніж з 3 літер алфавіту { a, b, c, d }. Кількість n-літерних слів дорівнює кількості розміщень з 4 літер на n місць з повтореннями — воно дорівнює 4ⁿ. Кількість всіх слів буде складатися з кількостей одно-, дво- і трибуквених слів. Тоді відповідь на початкове питання буде 4¹ + 4² + 4³ = 84.

Застосування

В теорія множин, цей принцип множення часто визначається як добуток кардинальних чисел. Ми отримуємо

$|S_{1}|\cdot |S_{2}|\cdots |S_{n}|=|S_{1}\times S_{2}\times \cdots \times S_{n}|$

де х це декартів добуток множин.

Див. також

• Комбінаторики
• Розміщення з n по k
• Перестановки множини
• Комбінації з n по k
• Комбінаторні принципи