АЛГЕБРА І ПОЧАТКИ АНАЛІЗУ

Розділ IV. ЕЛЕМЕНТИ КОМБІНАТОРИКИ, ПОЧАТКИ ТЕОРІЇ ЙМОВІРНОСТЕЙ ТА ЕЛЕМЕНТИ СТАТИСТИКИ

§1. ЕЛЕМЕНТИ КОМБІНАТОРИКИ.

1. Правило суми і правило добутку

Багато комбінаторних задач можуть бути розв’язані за допомогою двох важливих правил, які називають відповідно правило суми і правило добутку.

Спочатку розглянемо правило суми:

якщо деякий елемент А можна вибрати m способами, а елемент В — r способами (причому будь-який вибір елемента А відрізняється від вибору елемента В), то вибрати А або В можна m + r способами.

Приклад 1. В ящику знаходиться 7 білих і 4 чорних кульки. Тоді вибрати одну кульку: білу або чорну можна 7 + 4 = 11 способами.

Зрозуміло, що правило суми можна розповсюдити на три і більше елементів.

Сформулюємо правило добутку:

якщо деякий елемент А можна вибрати m способами, а після кожного такого вибору інший елемент В можна вибрати (незалежно від вибору елемента А) — r способами, то пару об’єктів А і В можна вибрати mr способами.

Приклад 2. У шкільній їдальні є вибір з 3 перших і 5 других блюд. Тоді обід з першого і другого блюда можна обрати 3 ∙ 5 = 15 способами.

Правило добутку розповсюджується на три і більше елементів.

Приклад 3. Скільки трицифрових чисел можна скласти з цифр 1; 2; 3; 4; 5, якщо в числі: 1) цифри не повторюються; 2) цифри повторюються.

Розв’язання.

1) Маємо 5 способів для сотень числа (мал. 129). Після того, як місце сотень заповнене (наприклад, цифрою 1), для десятків залишається 4 способи. Міркуючи далі, для одиниць - 3 способи. Отже, маємо: «5 способів, і після кожного з них — 4, і після кожного з них — 3 способи». За правилом добутку маємо 5 ∙ 4 ∙ 3 = 60 чисел.

2) Якщо цифри у числі повторюються, то на кожне з трьох місць є по 5 варіантів заповнення (мал. 130), і тоді всіх чисел буде 5 ∙ 5 ∙ 5 = 125.

Приклад 4. Скільки парних чотирицифрових чисел можна скласти з цифр 6; 7; 8; 9, якщо в числі цифри не повторюються?

Розв’язання. Парне чотирицифрове число можна отримати, якщо останньою цифрою буде 6 або 8. Чисел, у яких остання цифра 6 буде З ∙ 2 ∙ 1 = 6 (мал. 131), чисел, у яких остання цифра 8 буде також 6. За правилом суми всього парних чисел, що задовольняють умові, буде 6 + 6 = 12.