Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Тема 5. Комбінаторний аналіз



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

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

Розглянемо такий приклад. Нехай множина М складається з елементів трьох типів: k елементів 1-го типу, м елементів 2-го типу та l елементів 3-го типу. Очевидно, що для вибору одного елемента 1-го типу існує рівно k способів, для вибору елемента другого типу — m способів та для вибору елемента 3-го типу — l способів. Кількість варіантів для вибору одного елемента першого або другого типу дорівнює k + m, для вибору спочатку елемента 1-го типу, а потім елемента другого типу (всього двох елементів у заданій послідовності) існує k ´ m можливостей.

Під час розв’язання задач комбінаторного аналізу використовуються два основні аксіоматичні правила.

Правило суми. Якщо елемент а може бути вибраний k способами, а елемент b — іншими m способами, то вибір a або b може бути здійснений k + m способами.

Правило добутку. Якщо елемент a може вибиратися k способами, а після кожного з цих виборів елемент b вибирається m способами, то вибір пари елементів (a, b) у такій послідовності буде здійснений k ´ m способами.

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

Перестановка (або розміщення) — це впорядкована вибірка елементів з деякої множини S.

Сполучення — невпорядкована вибірка елементів з деякої множини S.

У перестановках можна як допускати, так і не допускати повторення. Так, вибираючи два з трьох елементів a, b, c, ми можемо вибрати, наприклад, спочатку будь-який елемент, наприклад а, а потім будь-який елемент з тих, що лишилися, наприклад b. Таким чином ми отримали один елемент вибірки. Якщо ж вибрати всі можливі елементи за описаною процедурою, то отримаємо вибірку, яка буде називатись перестановкою без повторень, якщо вважати порядок елементів істотним (тобто елемен­ти ab та ba вважаються різними) або ж сполученням без повторень, якщо вважати порядок елементів неістотним (тобто елементи ab та ba вважаються однаковими). Щоб отримати перестановки та сполучення з повтореннями в описаній процедурі, на другому кроці необхідно вибирати будь-який елемент з множини (а не лише з тих елементів, що лишилися після вибору елемента а).



У результаті проведення наведеної процедури отримуємо дев’ять перестановок з повтореннями:

aa, ab, ac, ba, bb, bc, ca, cb, cc

та шість перестановок без повторень:

ab, ac, ba, bc, ca, cb.

Маємо також шість сполучень з повтореннями:

aa, ab, ac, bb, bc, cc

та три сполучення без повторень:

ab, ac, bc.

Кількість перестановок без повторень з n елементів по m позначимо . Цю кількість досить легко обчислити. Справді, в перестановці a1a2…am ми можемо як a1 взяти будь-який з n елементів, а як a2 — будь-який з інших n — 1 елементів і т.д. Отримаємо:

Для чисел виконується рекурентне співвідношення:

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

Зауважимо, що

Кількість перестановок з повтореннями з n елементів по m дорівнює nm, оскільки в a1a2…aп для кожного з a1, a2, , am існує n можливостей вибору.

Кількість сполучень з повтореннями з n елементів по m дорівнює:

Важливу роль у комбінаторному аналізі відіграють твірні функції.

Якщо u0, u1, …, un, … — деяка послідовність чисел, то їй можна поставити у відповідність твірну функцію g(x), що визначається таким чином:

g(x) = u0 + u1x + u2x2 + … +unxn + …

Якщо цей ряд має круг збіжності радіусу R > 0, то в деякому разі властивості функції g(x) уможливлять обчислення коефіцієнтів un (або хоча б оцінювання порядку їх величини) чи отримання іншої цінної інформації.

Нехай h(x) — твірна функція для ряду v0, v1, …, vn, …, тоді



cg(x) + dh(x) = (cu0 + dv0) + (cu1 + dv1)x + + (cu2 + dv2)x2 + … +(cun + dvn)xn + … g(x)h(x) = w0 + w1x + w2x2 + … +wnxn + … (1)

де wn = u0vn + u1vn–1 + … + un–1v1 + unv0, для будь-якого n = 1, 2, 3, …

Отже, визначені операції додавання, множення на скаляр та множення рядів задовольняють закони асоціативності, комутативності та дистрибутивності. Крім того, якщо u0 ¹ 0 та якщо вважати, що v0 = u0–1, то вираз (1) можна використовувати як рекурентне співвідношення для визначення таких v1, v2, ..., що g(x)h(x) = 1.

Термінологічний словник

Кількість перестановок без повторень з n елементів з по m:

Кількість перестановок з повтореннямз n елементів по m дорівнює nm.

Кількість сполучень без повтореньз n елементів по m:

Кількість сполучень з повторенням з n елементів по m дорівнює:

Перестановка (або розміщення) — це впорядкована вибірка елементів з деякої множини S.

Правило добутку. Якщо елемент a може вибиратися k способами, а після кожного з цих виборів елемент b вибирається m способами, то вибір пари елементів (a, b) у такій послідовності буде здійснений k × m способами.

Правило суми. Якщо елемент а може бути вибраний k способами, а елемент b — іншими m способами, то вибір a або b може бути здійснений k + m способами.

Сполучення — невпорядкована вибірка елементів з деякої множини S.

Твірна функція g(x) — степеневий ряд g(x) = u0 + u1x + u2x2 +
+ … +unxn + …, що ставиться у відповідність числовій послідовності u0, u1, …, un, …

Практичне заняття


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!