У повсякденному житті дуже часто доводиться стикатися з математикою. Хоча зазвичай це не помітно. Коли ви йдете у магазин за покупками та обираєте певні продукти з всіх можливих, то ви зустрічаєтесь з математичним поняттям «ймовірність», а коли готуєте бутерброд і робите один з ковбасою, інший з шинкою, то це «комбінаторика». Адже ви комбінуєте компоненти бутерброду, складаєте його в різному порядку. Розглянемо ці поняття детальніше.

Для кращого розуміння вам варто ознайомитися з поняттям множин.

Елементи комбінаторики

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

Розглянемо правило «суми»:

Якщо деякий елемент «А» можна вибрати «n» способами, а елемент «В» - «m» способами (елементи «А» та «В» є різними), то вибрати елемент «А» АБО «В» можна «n + m» способами.

Наведемо приклад. У вас є «5» синіх ручок (Елемент «А» це «синя ручка», відповідно є «5» варіантів вибору «n = 5»), «7» чорних ручок (Елемент «В» - «чорна ручка», відповідно маємо «7» варіантів вибору «m = 7») та «2» червоні (Припустимо у нас ще є третій елемент «С» - «червона ручка» і маємо «2» варіанти вибору «k = 2»). Нам необхідно обрати одну ручку. Зауважте! Не має значення якого кольору вона має бути. В такій ситуації обрати одну ручку ми можемо «5 + 7 + 2 = 14» способами (оскільки, беремо будь-яку з доступних).

Розглянемо правило «добутку»:

Якщо деякий елемент «А» можна вибрати «n» способами, а після кожного такого вибору (тобто, не має значення який елемент «А» ви виберете) можна вибрати елемент «В» - «m» способами, то ПАРУ елементів «А» та «В» можна вибрати «n ∙ m» способами.

Наведемо приклад. В магазині є «5» зошитів (Елемент «А» це «зошит» і кількість їх вибору «5», «n = 5») та «9» ручок (Елемент «В» - «ручки», їх кількість «9», «m = 9»). Вам потрібно обрати один зошит та одну ручку (тобто, створити пару з елемента «А» та «В»). Зауважимо, що вибір одного елемента не буде залежати від вибору іншого. Тобто, який би зошит ми не обрали до нього в пару ми можемо взяти будь-яку з доступних ручок. Тому, пару із зошита та ручки ми можемо створити (обрати) «5 ∙ 9 = 45» способами.

Завдань які використовують правило добутку на справді доволі багато.

Наприклад, розв’яжемо декілька з них:

Завдання 1: У їдальні є «3» перші страви, «5» других і «2» треті страви. Скількома способами можна скласти з них обід?

Отже, ми маємо три елементи (перша, друга, третя страва). І нам потрібно вказати скількома по одному елементу з кожного (з кожної страви) і при цьому вибір одного елементу не впиває/залежить від вибору іншого елементу. Тому, обід ми можемо скласти «3 ∙ 5 ∙ 2 = 30» способами.

Завдання 2: Скільки чотирицифрових чисел, кратних «5», у яких усі цифри різні, можна записати, використовуючи цифри «5», «6», «7», «8», «9»?

Давайте пригадаємо ознаку ділення числа на «5». Для того щоб число ділилося на «5» його остання цифра має бути «0» або «5». З доступних нам цифр ми маємо «5». Тому, наше чотирицифрове число буде закінчуватися на «5». Відповідно це означає, що ми вже не можемо використовувати «5» (бо цифри мають не повторюватися) і нам потрібно обирати лише з цифр «6», «7», «8», «9». При цьому оскільки остання цифра числа вже буде не змінна, то потрібно буде заповнити лише чотири передні цифри.

В такій ситуації наше чотирицифрове число можна записати у вигляді: «xyz5», де «x», «y», «z» це одна з доступних цифр («6», «7», «8», «9»).

Почнемо з «х». На його місце ми можемо поставити будь-яку доступну цифру. Оскільки їх є «4», то це і буде нашою кількістю вибору (в теорії записували як «n»); «n = 4». Але після того, як ми виберемо одну цифру їх кількість зменшиться (бо вони мають не повторюватися).

Тоді, на місті «у» може стояти лише одна з трьох доступних цифр; «m = 3». А, на місці «z» лише одна з двох доступних; «k = 2».

Тому, записати таке чотирицифрове число ми можемо «n ∙ m ∙ k» способами. Тобто, «4 ∙ 3 ∙ 2 = 24».

Поняття факторіалу

Звісно ж, краще розпочати з теорії.

Факторіалом числа «n», де «n» - ціле невід’ємне число (тобто, «0», «1», «2», …), називають добуток (множення) усіх натуральних чисел (тобто, «1», «2», «3», …) від «1» до «n».

Факторіал числа «n» записують так «n!». Факторіал нуля («0!») вважається рівний «1», тобто «0! = 1».

n! = 1 ∙ 2 ∙ 3 ∙ … ∙ (n-1) ∙ n

Наприклад: Обчислити «6!».

6! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720

Спростити вираз: «/7!/5!».

/7!/5! = /1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7/1 ∙ 2 ∙ 3 ∙ 4 ∙ 5

Як помітно, у чисельнику та знаменнику у нас є однакові множники «1 ∙ 2 ∙ 3 ∙ 4 ∙ 5». Враховуючи це ми можемо їх скоротити:

/1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7/1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 6 ∙ 7 = 42

Перестановки

Якщо з деякої множини (набору елементів), що складається з «n» елементів, вибрати всі «n» елементів (тобто, взяти/використати їх усіх) і скласти з них упорядковану множину (поставити/розставити їх у певному порядку), то така вибірка називається «перестановкою з «n» елементів». При цьому, перестановки з «n» елементів відрізняються одна від одною лише порядком елементів.

Наприклад, ми можемо взяти множину «А» з елементами «{1, 2, 3}» («А = {1, 2, 3}»). Та скласти з неї (з її елементів) такі перестановки: «1 2 3», «1 3 2», «2 1 3», «2 3 1», «3 1 2», «3 2 1».

Кількість перестановок позначають «P_n», де «n» це кількість елементів (елементи початкової множини).

Кількість перестановок з «n» елементів можна знайти за формулою:

P_n = n!

Перестановка за своїм принципом дуже схожа на правило добутку. По факту єдина різниця між ними це те, що у правилі добутку ми маємо множення довільних чисел, а у перестановці від «1» до «n».

Завдання 1: Скількома способами можна скласти список з «8» учнів?

Враховуючи, що ми маємо «8» учнів, то відповідно це і буде кількістю наших елементів («n = 8»). Списки учнів будуть відрізнятися лише порядком запису. Тому, ми будемо мати перестановку з восьми елементів.

P₈ = 8! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 = 40320

Завдання 2: Обчислити «P₃ + P₄ - P₁₀P₈»

Відразу зауважимо, що «P_n = n!». Враховуючи цю умову будемо мати:

3! + 4! - /10!/8!

Після чого ми можемо скористатися правилом факторіалу:

3! + 4! - /10!/8! = 1∙2∙3 + 1∙2∙3∙4 - /1∙2∙3∙4∙5∙6∙7∙8∙9∙10/1∙2∙3∙4∙5∙6∙7∙8 = 6 + 24 - 9∙10 = 30 - 90 = -60

Завдання 3: Обчислити «P₅ - 2∙P₄P₃».

Відразу зауважимо, що «P_n = n!». Враховуючи цю умову будемо мати:

/5! - 2∙4!/3!

Також, враховуючи умови «5! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5» і «4! = 1 ∙ 2 ∙ 3 ∙ 4», то ми можемо зауважити, що «5! = 4! ∙ 5». Відповідно, ми можемо записати ще так: «5! = 3! ∙ 4 ∙ 5» і «4! = 3! ∙ 4». Тому, ми будемо мати:

/5! - 2∙4!/3! = /3!∙4∙5 - 2∙3!∙4/3!

Як помітно, у чисельнику є спільні множники. Винесемо їх за дужки:

/3!∙4∙5 - 2∙3!∙4/3! = /3! ∙ 4 ∙ (5 - 2)/3! = /3! ∙ 4 ∙ 3/3! = /3! ∙ 12/3!

Враховуючи, що в чисельнику та у знаменнику є «3!», то ми можемо їх скоротити:

/3! ∙ 12/3! = 12

Завдання 4: Скільки різних чотирицифрових чисел можна скласти з цифр «0, 4, 7, 8»?

Зауважимо, що нам дано лише чотири цифри і потрібно утворити чотирицифрове число. Тобто, нам необхідно виконувати перестановку даних цифр. Але оскільки, серед доступних цифр є нуль, то ми не можемо враховувати ті цифри в яких нуль стоїть першим.

Одним із варіантів розв’язання даної задачі буде схожим до «завдання 2» із правила добутку. Нам необхідно буде поставити в якості першої цифри ліворуч будь-яку з доступних крім «0». Таких варіантів буде «3». На другу позицію в нас теж буде три варіанти (оскільки, тут «0» ми вже можемо використовувати). На третю позицію буде «2» варіанти і відповідно на четверту лише «1».

Тому, ми зможемо скласти «3 ∙ 3 ∙ 2 ∙ 1 = 18» чотирицифрових чисел.

Другий варіант це скористатися правилом перестановки. Дізнаємося скільки можна скласти чисел з чотирьох цифр (нуль враховуємо), а після цього віднімемо кількість чисел які можна скласти з трьох цифр (тобто, вважаючи, що першою є «0», а три інші є перестановкою).

Тому, ми можемо це записати так:

P₄ - P₃ = 4! - 3! = 3!∙4 - 3! = 3!(4 - 1) = 3! ∙ 3 = 18

Як бачимо результати вийшли однаковими.

Розміщення

Будь-яка впорядкована підмножина (вибірка) «А» з «m» елементів множини «В» яка містить «n» елементів («m ≤ n»), називається «розміщенням із «n» по «m» елементів». При чому, дві такі підмножини вважаються різними, якщо вони відрізняються складом або порядком елементів.

Розміщення позначають так: «A/n/m».

Розміщення шукають за формулою:

A/n/m = /n!/(n - m)!

При цьому:

A/n/n = P_n

По факту, розміщення відрізняється від перестановки тим, що ми використовуємо не всі елементи з усіх доступних.

Для прикладу, якщо ми маємо множину чисел «{1, 2, 3}», то можемо скласти такі підмножини з двох елементів: «{1, 2}», «{1, 3}», «{2, 1}», «{2, 3}», «{3, 1}», «{3, 2}».

Запам’ятайте! У розміщенні підмножини можуть відрізнятися порядком. І підмножини «{1, 2}» та «{2, 1}» вважаються різними. Це допоможе вам відрізняти «розміщення» від «комбінації» яку розглянемо пізніше.

Завдання 1: Скільки чотирицифрових чисел можна утворити з цифр «1, 3, 5, 7, 9», якщо цифри в числі не повторюються?

Ми маємо скласти чотирицифрове числа. Тому, необхідно буде використати «4» цифри. Усього ми маємо «5» цифр з яких нам потрібно скласти дане число. При цьому числа «1357» і «1375» вважаються різними. Отже, ми маємо використати певну частину елементів з усіх наявних. При цьому утворені числа відрізнятимуться, якщо їх елементи мають різний порядок. Тому, нам необхідно використати формулу розміщення. Матимемо:

A/5/4 = /5!/(5 - 4)! = /5!/1! = 120

Завдання 2: У класі навчається «17» учнів. Скількома способами можна вибрати старосту та його заступника?

Враховуючи, що староста та заступник це різні посади, то відповідно буде важливо хто ким стане. Тому, ми можемо зробити висновок, що «Андрій - староста, Марія - заступник» і «Марія - староста, Андрій - заступник» будуть різними підмножинами. Тому, підмножини вважаються різними якщо порядок їх елементів є різним. При цьому ми беремо лише «2» елементи зі всіх доступних (з «17»). Отже, ми зможемо скористатися формулою розміщення:

A/17/2 = /17!/(17 - 2)! = /17!/15! = 16 ∙ 17 = 272

Комбінації (Сполучення)

Будь-яка впорядкована підмножина (вибірка) «А» з «m» елементів множини «В» яка містить «n» елементів («m ≤ n»), називається «комбінацією із «n» по «m» елементів». При чому, дві такі підмножини вважаються різними, якщо вони відрізняються складом елементів.

Розміщення позначають так: «C/n/m».

Розміщення шукають за формулою:

C/n/m = /n!/m!(n - m)!

Як помітно, розміщення та комбінація на справді дуже схожі. Їх відрізняють лише тим, що в комбінації не має значення порядок елементів. Тобто, підмножини «{1, 2, 3}» та «{1, 3, 2}» вважаються однаковими.

Розглянемо декілька властивостей комбінації:

Розглянемо декілька прикладів:

Завдання 1: Скільки існує звичайних правильних дробів, у яких чисельник і знаменник прості числа: «2, 3, 5, 7, 11, 13, 17, 19, 23»?

Під фразою «звичайний дріб» мається на увазі, що цей дріб не має цілої частини. Пригадаємо, що правильний дріб це дріб у якого чисельник є меншим за знаменник. Для того щоб скласти дріб нам необхідно взяти два числа. А, всього, ми маємо «9» чисел. При цьому числа «/2/3» та «/3/2» є різними. До того ж, ми маємо відкинути всі значення при яких дріб є не правильний. Враховуючи, що при одній комбінації чисельника і знаменника він буде правильним, а при змінні їх місцями вийде не правильним, то це можна буде прирівняти до умови, що «/2/3» та «/3/2» є однаковими множинами. В такій ситуації ми зможемо скористатися формулою комбінації.

Отже, матимемо:

C/9/2 = /9!/2!(9 - 2)! = /9!/2! ∙ 7! = /8 ∙ 9/2 = 36

Завдання 2: У класі навчається «17» учнів. Скількома способами можна вибрати трьох чергових?

Нам потрібно обрати «3» елементи з «17» доступних. При цьому підмножини «Віталій, Юлія, Сергій» та «Віталій, Сергій, Юлія» вважаються однаковими (якщо, ми говоримо про одних і тих же людей). Тому, підмножини мають відрізнятися своїм складом. Отже, ми маємо скористатися формулами комбінації:

C/17/3 = /17!/3!(17 - 3)! = /17!/3! ∙ 14! = /15 ∙ 16 ∙ 17/3! = 680