19.03.2020

Тема: Елементи комбынаторики .Вправи.

Багато теорем і формул комбінаторики ґрунтуються на так званих

правилах (принципах) суми і добутку.

Приклади

1. У групі 21 студент. Скількома способами можна вибрати в цій групі

трьох студентів для проходження виробничої практики на трьох підприємствах?

Розв’язання

Для першого підприємства можна вибрати будь-кого із студентів, тобто

таких можливостей 21, для другого підприємства таких можливостей вже 20 і

для третього – 19. Отже, всього можливостей для вибору групи з трьох

студентів 21×20×19=7980

Відповідь: 7980 способів.

2. У розіграші першості країни з волейболу бере участь 14 команд.

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

медалі?

Розв’язання

Золоту медаль може одержати одна з 14 команд. Після того як визначимо

володаря золотої медалі, срібну медаль може мати одна з 13 команд. Отже,

8

загальне число способів розподілення золотої і срібної медалі дорівнює

14×13=182.

Відповідь: 182 способи.

Міркування, що проводились під час розв’язування цих задач, дають

можливість сформулювати твердження, яке називають основним правилом

комбінаторики (правилодобутку).

Правило добутку:

Якщо об’єкт А можна вибратиn способами і при кожному з цих виборів

об’єкт В можна вибрати m способами, то вибір пари (А,В) можна здійснити

n×m способами.

Правило добутку можна узагальнити.

Узагальнене правило добутку:

Нехай об’єкт А1 можна вибрати m1 способами, об’єкт А2 –m2

способами,…, об’єкт Ак – mк способами. Тоді послідовний вибір об’єктів

(А1,А2,…,Ак) можна здійснити m1×m2×…mк способами .

Розглянемо комбінаторне правило додавання.

Правило суми:

Якщо деякий об’єкт А можна вибрати n способами, а об’єкт В – m

способами, причому ніякий вибір А не збігається з жодним з виборів В, то один

з об’єктів А або В можна вибрати n+m способами

Правило суми, як і правило добутку, також можна узагальнити для k

об’єктів.

Приклади розв’язання вправ

1. На вершину гори веде сім стежок. Скількома способами турист може

піднятися на гору і спуститися з неї. Дайте відповідь на це саме запитання, якщо

підйом і спуск потрібно здійснити різними стежками ?

Розв’язання

9

Стежку для підйому і стежку для спуску можна вибрати сімома

способами. Тому, за правилом добутку всіх способів 7×7=49 .

Якщо підйом і спуск потрібно здійснити різними стежками, то стежку для

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

одну із шести стежок. У цьому випадку буде 7×6=42 способи.

Відповідь: 49 способів; 42 способи.

2. Група студентів опановує сім навчальних дисциплін. На понеділок

планується заняття з чотирьох різних дисциплін. Скількома способами можна

скласти розклад на понеділок?

Розв’язання

На перше заняття можна вибрати одну із семи дисциплін. Цей вибір

можна здійснити сімома способами. На друге – одну із шести дисциплін можна

вибрати шістьма способами, на третє – одну з п’яти дисциплін п’ятьма

способами, на четверте – одну із чотирьох дисциплін чотирма способами.

Загальна кількість способів 7×6×5×4=840

Відповідь: 840 способів.

3. На диск сейфа нанесені 12 літер, а код складається із п’яти літер.

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

що він складається з п’яти літер ?

Розв’язання

Людині потрібно зробити п’ять дій: набрати першу літеру, потім другу і

т.д. Кожну з цих дій вона може зробити 12 способами, тому усіх невдалих спроб

може бути 12×12×12×12×12=125

=248832.

Відповідь: 248832спроб.

4. Нехай з пункту А до пункту В веде m доріг, з пункту А до С – n доріг,

з С до D – l доріг, з В до D – k доріг. Пункти В і С між собою дорогами не

сполучені. Скількома дорогами можна попасти з А до D ?

10

Розв’язання

Згідно з правилом добутку з пункту А до D через В веде mk доріг, через С

веде – nl доріг.

За правилом суми число всіх доріг із А до D – mk+nl.

Відповідь: (mk+nl ) доріг.

5. У кошику 12 яблук та 10 апельсинів. Олег вибирає або яблуко, або

апельсин. Після цього Надійка вибирає з фруктів, що залишилися, яблуко й

апельсин одночасно. Скільки можливостей такого вибору?

Розв’язання

Олег може вибрати яблуко 12 способами. Надійка яблуко і апельсин, для

кожного з виборів Олега, може вибрати 11×10 способами.

Якщо ж Олег одним із 10 можливих способів вибрав апельсин, то Надійка

вибрати яблуко й апельсин може вже меншим числом способів, а саме 12×9.

Використовуючи правило добутку та суми, одержимо 12×11×10+12×10×9=2100

способів.

Відповідь: 2100 способів.

6.На чергування в студентському гуртожитку може піти або студент з

кімнати №1, у якій проживають три студенти, або студент з кімнати №2, у якій

проживають два студенти. Скількома способами можна вибрати одного

студента на чергування в гуртожитку?

Розв’язання

Загальна кількість способів, якими можна вибрати на чергування одного

студента або з кімнати №1 або з кімнати №2, згідно зправилом сумибуде 3+2=5.

Відповідь:5 способів.