ТЕМА: Правило суми і правило добутку

Комбінаторика - важливий розділ математики, знання якого необхідні представникам різноманітних спеціальностей. З комбінаторними задачами доводиться мати справу фізикам, хімікам, біологам, лінгвістам, спеціалістам по кодах та інших.

Комбінаторикою називається розділ математики, в якому вивчаютьсяпитання про те, скільки різних сполук, що відповідаютьтим чи іншим умовам,

Комбінаторні методи лежать в основі вирішення багатьох задач теорії ймовірностей та її застосування.

З задачами, в яких доводиться вибирати ті чи інші предмети, розміщувати їх в певному порядку і відшуковувати серед різних розміщень найкращі, люди стикнулися ще в доісторичну епоху, обираючи найкращі розміщення мисливців під час полювання, воїнів під час битви, інструментів під час роботи. Певним чином розміщувалися прикраси на одязі, візерунки на кераміці.

З ускладненням виробничих і суспільних відносин ширше приходилося користуватися загальними поняттями про порядок, ієрархію, групування. В тому ж напрямку діяв розвиток ремесел торгівлі. Перша згадка про питання, близькі до комбінаторних, зустрічається в китайських рукописах, що відносяться до XII – XIII ст. до н.е. (точно датувати ці рукописи неможливо, тому що в 213 р. до н.е. імператор Цин Шихуан наказав спалити всі книги, тому до нас дійшли пізніше зроблені копії). В цих книгах писалося, що усе в світі являється поєднанням двох початків – чоловічого та жіночого. Серед предметів, покладених в піраміду, де 35 століть тому назад був похований єгипетський фараон Тутанхамон, знайшли розкреслену дощечку з трьома горизонталями і 10  вертикалями та фігурки для давньої гри , про правила якої ми, можливо, ніколи не дізнаємось.

Пізніше з’явились нарди, шашки й шахмати, а також їх різноманітні варіанти (китайські та японські шахмати, японські облавні шашки ); в кожній з цих ігор доводилося розглядати різноманітні комбінації фігур, що мали здатність пересовуватись, та вигравав той, хто їх краще вивчив, знав переможні комбінації та вмів уникати програшів.

Основоположниками ж сучасної комбінаторики є такі вчені: Яків Бернуллі, П’єр Ферма, Леонард Ейлер, Коші Огюстен, Жозеф Луї Лагранж.

Часто доводиться розв’язувати задачі, в яких потрібно вибирати з даної кількості елементів такі, що мають певні властивості, або розміщувати їх у певному порядку.

Наприклад, скільки пар чергових можна утворити з 24 учнів групи?

Скількома способами можна розмістити 8 гостей за столом? Скільки існує п’ятицифрових телефонних номерів?

Задачі такого виду називаються комбінаторними

Проблемне завдання:

З’ясувати, скільки різних “слів” можна скласти з букв с, н, і, якщо «словом» вважати будь-яке поєднання цих букв?

На це запитання відповісти неважко, адже букв усього три. Тому, перебираючи поєднання цих букв, можна сказати, що таких “слів” є 6.

Давайте в цьому переконаємося: ніс – перше слово, сні – 2-е, сін – 3-є, нсі – 4-е, існ – 5-е і інс – 6-е.

А якщо елементів у множині буде більше?

Щоб можна було розв’язувати комбінаторні задачі різних видів,

ознайомимося з основними комбінаторними правилами: правилом суми і правилом добутку.

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

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

Приклад. В ящику знаходиться 7 білих і 4 чорних кульки. Скількома способами можна вибрати одну кульку?

Розв’язання: вибрати одну кульку (білу, або чорну) можна 7 + 4 = 11(способами).

Відповідь: 11 способами.

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

Сформулюємо правило добутку: якщо деякий елемент А можна

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

Приклад . У училищній їдальні є вибір з 2 перших і 5 других страв.

Скількома способами можна обрати обід з першої та другої страв?

Розв’язання: обід з першої і другої страви можна обрати 2 ∙ 5 = 10

(способами).

Відповідь: 10-ма способами.

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

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

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

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

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

Приклад. Скільки трицифрових чисел можна скласти з цифр 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.

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

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

Домашнє завдання: Розв’язати задачі:

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

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