До виконання практичних завдань

ЕЛЕКТРОННИЙ ВАРІАНТ

Обговорено на засіданні кафедри ВМ та ЕММ

Протокол № 1 від 27.08. 2002 р.

Чернігів 2002

Вступ

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

Окремі комбінаторні задачі з’явилися дуже давно. У відомих тепер працях стародавніх індійських вчених знайдені формули числа перестановок і сполучень. В Європі елементи комбінаторики зустрічаються в працях Н. Тортальї (XVI ст.), але повної теорії перестановок, розміщень, сполучень він не дав. Перші теоретичні дослідження в цій галузі, у зв’язку з розвитком алгебри многочленів і виникненню теорії ймовірностей здійснили в XVII ст. французький математик Б. Паскаль (1623-1662) і П. Ферма (1601-1665). Ряд комбінаторних задач розв’язав Л. Ейлер (1707-1783). Проте в справжню математичну науку комбінаторика перетворилася лише в ХХ столітті, коли виникла потреба її застосування в обчислювальній техніці, кібернетиці, економіці й інших науках.

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

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

Поняття комбінаторної задачі.

У практичному житті, серед різних математичних задач часто зустрічаються такі, в яких треба вибирати з деякої множини об'єктів підмножини елементів, які мають ті чи інші властивості, розміщувати їх у певному порядку за певними правилами зна­ходити число способів, за якими таке розташування можна здійснити. Наприклад, керівнику підприємства треба надіслати у відрядження певну групу спеціалістів, агроному розмістити сільськогосподарські культури на декількох полях і т.д.

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

Розділ математики, в якому обґрунтовується теорія розв'язу­вання комбінаторних задач, називається комбінаторикою.

Будь-яку комбінаторну задачу можна звести до задачі про скінченні множини, тому комбінаторику можна розглядати як складо­ву частину теорії скінчених множин. Ми будемо вважати, що читач обізнаний з елементами теорії множин.

Спільним для всіх комбінаторних задач є те, що у кожній з них іде мова про деяку скінчену множину елементів і про кількість її підмножин, які задовольняють певні перелічені в умові вимоги умови.

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

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

Комбінаторні задачі поділяються на розміщення, перестановки і комбінації як без повторення, так 1 з повтореннями. У комбіна­ториці розроблені загальні методи і виведені готові формули для розв'язування комбінаторних задай, які ми далі розглянемо.

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

2.Загальні правила комбінаторики.

Правило суми. Якщо елемент а з множини А можна вибрати m способами, а елемент b множини В можна вибрати n способами, причому ніякий вибір a не збігається з жодним з виборів b, то число способів, якими можна здійснити хоча б один з цих виборів, дорівнює сумі m+n.

Правило суми легко узагальнюється.

Узагальнене правило суми. Нехай елемент а₁ множини А₁ можна вибрати m₁ способами, елемент а₂ множини А₂ - m₂ способами,..., елемент a_k - множини А_k можна вибрати m_k способами. Тоді число способів, якими можна здійснити хоча б один з цих виборів, дорівнює сумі m₁ + m₂ +...+ m_k.

Приклад 1. У спільному українсько-німецькому підприємстві працюють 100 робітників. З них 45 володіють англійською мовою, 65 – німецькою, 25 – англійською і німецькою мовами. Скільки працівників знають: а) хоча б одну мову?; б) тільки в одну мову; в) не знають жодної з них?

Розв'язання. U-множина працівників фірми

Рис. 1

. а) Нехай А - множина працівників, що володіють англійською мовою, їх число N(А)=45; В - множина працівників, що володіють

німецькою мовою, їх число N(В)=65.

Число працівників, що знають і англійську і німецьку є число елементів

перерізу множин А і В, тобто N (А∩В)=25. Тоді за правилом суми число

працівників які володіють хоч би однією мовою буде дорівнювати

N(A)+N(B)- N (А∩В),

тобто 45+65-25-85 (працівників). Отже, хоча б в однією мовою володіють 85 працівників.

б) Тільки англійською 45-25=20 (працівників), тільки німецькою 65-25=40 (працівників).

За правилом суми число студентів, що грають тільки в одну гру, дорівнює сумі 20+40=60 (студентів).

в) Не знають жодної з цих іноземних мов 100-85=15(працівників).

Відповідь. а) 85 працівників, б) 60 працівників, в) 15 працівників. Ілюстрація кругами Ейлера на рис.1.

Правило добутку. Якщо елемент а множини А можна вибрати m способами i при кожному а цих виборів елемент b множини В можна вибрати n способами, то упорядковану пару (а;b) можна вибрати m×n способами.

У справедливості правила добутку можна переконатись з таких міркувань. Нехай А=(а₁,а₂,…,а_m) і В=(b₁,b₂,…,b_m).

Тоді пари виду (а,b) можна записати у вигляді такої таблиці:

(а₁;b₁), (а₁;b₂),…, (а₁;b_n),

(а₂;b₁), (а₂;b₂),…, (а₂;b_n),

…………………………

(а_m;b₁), (а_m;b₂),…, (а_m;b_n).

Ця таблиця складається з m рядків, у кожному з яких міститься n елементів. Отже, загальне число пар дорівнює добутку m×n.

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

Правило добутку легко узагальнюється на випадок кількох ви­борів.

Узагальнене правило добутку. Нехай елемент а₁ з множини А₁, можна вибрати m₁ способами, елемент а₂ з множини А₂ - m₂ спосо­бами,..., елемент а_k з множини A_k можна вибрати m_k способами.

Приклад 2. З Києва до Чернігова можна дістатися пароплавом, потягом, автобусом, літаком. З Чернігова до Новгород-Сіверського пароплавом і автобусом. Скількома способами можна здійснити подорож за маршрутом Київ-Чернігів-Новгород-Сіверський?

Розв'язання. Позначимо множину можливих способів подорожі від міста Києва до міста Чернігова через М, в ній чотири елементи, тому вибрати один елемент – спосіб подорожі, можна чотирма способами, тобто m=4. Множину можливих способів подорожі з міста Чернігова до міста Н.-Сіверський позначимо через Р, в ній 2 елементи, тому вибрати один елемент з цієї множини можна двома способами, тобто n=2.

Тоді за правилом добутку число способів вибору упорядкова­ної пари дорівнює добутку m×n=4×2=8. Отже, з міста Києва до міста Н.-Сіверського через місто Чернігів можна вибрати 8 способів подорожі.

3. Розміщення

Означення. Кожна упорядкована m-елементна підмножина n-елементної множини, називається розміщенням з n елементів по m еле­ментів.

З означення випливає, що n³m³0 і що розміщення з n елемен­тів по m елементів - це всі m-елементні підмножини, які відріз­няються між собою або складом елементів або порядком їх сліду­вання.

У комбінаторних задачах необхідно вміти підраховувати число всіх розміщень з n елементів по m елементів.

Для позначення числа розміщень з n елементів по m елементів вживають спеціальний символ (читається: "число розміщень з n по m" або "А із n по m"). А - перша буква французького слова аrrangement, що означає в перекладі розміщення, зведення до поря­дку.

Зрозуміло, що =1, бо існує лише одна підмножина n-елементної множини, яка не містить елементів (порожня множина). У загальному випадку має місце таке твердження.

Теорема 1. Число розміщень з n елементів по m елементів до­рівнює добутку m послідовних натуральних чисел від n до n-m+1 включно, тобто

= n(n-1) (n-2) … (n-m+1), m>0(1)

Доведення. Число розміщень з n елементів по m елементів до­рівнює числу всіх m-елементних упорядкованих підмножин n-елементної множини. Перший елемент підмножини можна вибрати n спо­собами. Другий елемент підмножини можна вибрати n-1 способами, оскільки другим елементом можна взяти будь-який елемент множини, крім уже вибраного першим. Кожний із способів вибору першого елемента може об'єднуватись з кожним із способів вибору другого, тому існує n(n-1) способів вибору перших двох елементів для n-елементної упорядкованої підмножини.

Після вибору перших двох елементів залишається n-2 можли­востей вибору третього елемента, і знову, як і раніше, кожна а цих можливостей може комбінуватись з будь-якою із можливостей вибору перших двох елементів, тобто вибір перших трьох елементів можна здійснити n(n-1)(n-2) способами і т.д.

Останній m-й елемент m-елементної упорядкованої підмножини n-елементної множини можна вибрати n-m+1 способом, оскільки до вибору m-го елемента залишилось n-(m-1) елементів.

Отже, число розміщень з n елементів по m елементів дорівнює

= n(n-1) (n-2) … (n-m+1),

що й треба довести.

Цю теорему можна довести Іншими способами, зокрема методом математичної індукції.

Формулу (1) можна записати в іншому вигляді, використовуючи поняття n-факторіала. Дійсно, домножимо і розділимо добуток, що стоїть у правій частині формули (1), на (n-m)!

Дістанемо

або (2)

Формула (2) має деякі переваги перед формулою (1) у практичному використанні.

Формула (1) виводилась у припущенні, що m>0, а формулою (2) мож­на користуватись і при m=0, оскільки вона і в цьому випадку дає вірний результат:

Нагадаємо, що =1, а порожня множина є єдиною підмножиною будь-якої множини.

При виведенні формули (1) також припускалось, що n¹0, тоб­то, що дана множина не порожня. Якщо n=0, то розглядається по­рожня множина. Оскільки порожня множина має тільки одну підмножину (саму себе), то

=1

Враховуючи, що 0!=1, то формула (2) дає вірний результат і при n=0:

Приклад 1. Розклад одного дня містить 5 різних пар. Знайти кількість можливих розкладів, якщо вивчається 9 дисциплін.

Розв'язання. Маємо розміщення з 9 елементів по 5 без пов­торень, їх кількість дорівнює

=9×8×7×6×5=15120

Відповідь. 15120.

У розміщеннях без повторень не має однакових елементів у виборці: після вибору першого елемента для вибору другого еле­мента залишається на одиницю менше можливостей i т.д.

Означення. Розміщенням з повтореннями з n елементів по m елементів називається будь-який упорядкований m-елементний набір виду (а₁,а₂,…,а_m), де а₁,а₂,…,а_m - елементи множини М=(а₁,а₂,…,а_n), в якому хоч би один елемент повторювався.

Число всіх розміщень з повтореннями з n елементів по m елементів позначають символом . На відміну від розміщень без пов­торень, де m£n, для розміщень з повтореннями може бути і m>n. Особливістю розміщень з повторенням е те, що після вибору першого елемента а₁ (М_i, записавши його на першому місці набору, його повертають у множину М, тобто число елементів множини М за­лишається сталим для вибору другого, третього і т.д. m-го еле­мента набору. Повторивши цю операцію m разів, дістаємо деяке розміщення з повтореннями з n елементів по m елементів. Тому розміщення з повтореннями з n елементів по m елементів ще нази­вають впорядкованими m-вибірками з n-елементної множини.

Теорема 2. Число розміщень з повтореннями з n елементів по m елементів обчислюють за формулою

= n^m, (3)

де m і n - натуральні числа.

Доведення. Перш за все відмітимо, що розміщення з повторен­нями з n елементів по m елементів можна одержати з розміщень по (m-1) елементу приєднанням ще одного елемента. Оскільки до кож­ного розміщення по (m-1) елементів можна приєднати будь-який з n елементів, то кожне розміщення по (m-1) елементу породжує n різ­них розміщень по m елементів, тобто

. (4)

Тепер доведення формули (3) проведемо методом математичної ін­дукції по m.

1) При m=1 число розміщень дорівнює n:

2) Припустимо, що формула (3) вірна для деякого m=k, тобто, що

3) Доведемо, що при цьому формула (3) вірна також і для m=k+1,

тобто, що

.

Дійсно, користуючись формулою (4), знайдемо:

.

4) Вимоги математичної індукції виконуються, тому формула (3) вірна для будь-якого натурального значення m.

Наслідок. Число підмножин n-елементної множини дорівнює 2ⁿ. Дійсно, нехай маємо множину М=(а₁,а₂,…,а_n), елементи якої пе­ренумеровані. Кожну підмножину множини М можна подати у вигляді упорядкованої n- елементної множини, елементами якої є нулі і одиниці, причому одиницю ставимо на тому місці, на якому знахо­диться певний елемент множини М, а нуль тоді, коли елемент мно­жини М не входить у підмножину. Наприклад, якщо М=(а₁,а₂,a₃,а₄), то набір (0;1;1;0) показує, що маємо підмножину (а₂,a₃), набір (0;0;0;0) - порожня множина, а набір (1;1;1;1) - це вся множина М.

Звідси випливає, що знайти число підмножин n-елементної множини М - це все одно, що знайти число перестановок з n елементів з повтореннями, 2-елементної множини (0;1). За формулою (1) число таких перестановок дорівнює 2ⁿ.

Приклад 2. До шестицифрових номерів телефонів входять цифри від О до 9. Скільки абонентів може обслуговувати телефонна станція?

Розв'язання. Оскільки цифри в номерах можуть повторюватись, то кількість шестицифрових номерів телефонів дорівнює числу роз­міщень з 10 елементів по 6 з повторенням, тобто

Відповідь. 1000000 абонентів.

Приклад 3. У селі проживає не менше 1000 жителів. Довести, що принаймні двоє з них мають однакові ініціали.

Розв’язання. В українському алфавіті 29 букв, які можуть бути ініціалами людини. Кількість всіх можливих різних пар ініціалів дорівнює числу розміщень з 29 букв з повтореннями, тобто

Відповідь. 841 різних пар ініціалів.