Презентація на тему:
"Комбінаторика"

Комбінаторика

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

Найпростішими прикладами комбінаторних конфігурацій є перестановки, розміщення, комбінація та розбиття. Комбінаторика пов'язана з багатьма іншими розділами математики. Термін «комбінаторика» ввів Лейбніц, який у 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво». Іноді під комбінаторикою розуміють більш широкий розділ дискретної математики, що включає теорію графів.

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

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

У комбінаториці є декілька задач, які вирішуються послідовно одна за одною. Перша з них спочатку формулює вимоги до класу комбінаторних конфігурацій, які потрібно побудувати. Доводиться, що хоча б одна така конфігурація існує, попри те, що побудувати таку конфігурацію може бути досить непросто. Тому інколи буває достатньо теоретичного доведення її існування. Після розв'язання першої задачі комбінаторики розв'язується не менш важлива друга — задача переліку комбінаторних об'єктів, які відповідають вихідним правилам їх побудови. Саме на розв'язання цієї задачі спрямовані сьогодні зусилля багатьох учених. Є досить багато задач, які так чи інакше стосуються цієї загальної задачі. Наприклад, до неї належить питання про кількість різних способів, якими можна розмістити групу студентів з 30 чоловік на 30 чи більше місцях, або про кількість способів проведення матчів з футболу між 10 різними командами?

Далі на основі отриманих розв'язків конкретних задач з переліку комбінаторних об'єктів розв'язується третя задача комбінаторики — це її побудова. Наприклад, потрібно не лише підрахувати кількість можливих варіантів розподілу 30 студентів на 30 місцях, а й побудувати всі ці розподіли або деякі з них у вигляді їх комбінаторних конфігурацій. Також може виникнути потреба побудувати таблицю матчів між 10 футбольними командами, а не тільки знати їх кількість. Четверта і остання задача комбінаторики — це задача про пошук серед комбінаторних конфігурацій такої, яка б приводила деяку функцію до оптимуму. Це на сьогодні досить нелегка для розв'язання загальна задача. Вона містить задачі комбінаторної оптимізації, наприклад, задачу комівояжера, яка на сьогодні ще не має остаточного розв'язання.

Основне правило комбінаторики Нехай необхідно виконати послідовно k дій. Якщо першу дію можна виконати n1 способами, другу - n2 способами і так далі до k-ї дії, яку можна виконати nk способами, то всі k дій можна виконати n1 · n2 · ... · nk способами.

Приклад 1. Скількома способами на першості світу з футболу можуть розподілитися медалі, якщо у фінальній частині грають 24 команди? Розв'язок. Золоту медаль може одержати будь-яка з 24-х команд, тобто 24 можливості. Срібну медаль може виграти одна з 23-х команд, а бронзову - одна з 22-х команд. За основним правилом комбінаторики загальне число способів розподілу медалей 24 · 23 · 22 = 12144. Скорочення n!=1 · 2 · 3 · ... · (n-1) · n називається факторіалом числа n (читається n-факторіал). Упорядковані множини, які відрізняються одна від одної лише порядком своїх елементів (тобто можуть бути одержані з однієї і тієї ж множини лише перестановкою своїх елементів), називаються перестановками. Позначимо число всіх перестановок n-елементної множини Pn.

Приклад 2. Скількома різними способами можна розмістити п'ять книжок на книжковій полиці? Розв'язок. Шукане число розміщень є числом способів упорядкування множини з п'яти елементів. Значить, це число дорівнює P5 = 1 · 2 · 3 · 4 · 5 = 120. Число різних m-елементних підмножин n-елементної множини становить Число Cnm називається числом комбінацій або сполучень із n елементів по m елементів. Кількість упорядкованих m-елементних підмножин n-елементної множини, всі m елементів якої різні, становить

Приклад 3. Скількома різними способами можна розмістити п'ять учнів в аудиторії, яка має 20 місць? Розв'язок. Шукане число способів дорівнює числу розміщень із 20 елементів, по 5 елементів, тобто A205 = 16 · 17 · 18 · 19 · 20 = 1860480. Кількість різних комбінацій із n елементів по m елементів з повтореннями становить

Біном Ньютона Рівність (a + b)n = Cn0 an b0 + Cn1 an-1 b1 + Cn2 an-2 b2 + ... +Cnn a0 bn називають біномом Ньютона. Біноміальні коефіцієнти можна виписати у вигляді трикутної таблиці, яка носить назву трикутника Паскаля: У n-му рядку трикутника Паскаля стоять коефіцієнти розкладу (Cnk) з бінома Ньютона, причому кожний коефіцієнт, крім двох крайніх, які дорівнюють 1, — це сума відповідних коефіцієнтів із попереднього рядка.

Основні властивості біноміальних коефіцієнтів Формула симетрії Формула додавання Формула суми всіх біноміальних коефіцієнтів Формула винесення за дужки

Презентацію підготувала учениця 11-Б класу Безсмертна Вікторія 2014 р.