На головну

розбиття

  1. Доведіть, що для даного розбиття відрізка нижня (верхня) сума є точною нижньою (верхньою) межею безлічі інтегральних сум.
  2. Межа інтегральних сум при прагненні діаметра розбиття до нуля
  3. Розбиття множин.

Розбиття не були розглянуті серед типових комбінаторних конфігурацій, тому що отримати для них явну формулу не так просто, як для інших.

Нехай є розбиття множини Х з m елементів на n підмножин:

,,, При

Підмножини називаються блоками розбиття.

Між розбивками і відносинами еквівалентності існує взаимнооднозначное відношення. Якщо і - два розбиття Х, то кажуть, що розбиття є подрібнення розбиття, якщо кожен блок є об'єднання блоків.

якщо k= 2, впорядковане розбиття множини М на два підмножини, що мають відповідно і елементів, визначається поєднанням (без повторень) з n елементів по або з n елементів по (). Отже, число розбиття R(,) Дорівнює біномінальної коефіцієнту. Таким чином,

У загальному випадку число впорядкованих розбиттів (), для яких, так само, а число R (n, k) упорядкованих розбиття на k підмножин обчислюється за формулою

Числа називаються поліноміальними коефіцієнтами, оскільки для всіх справедливо співвідношення

Приклад. У студентській групі, що складається з 25 чоловік, при виборі старости за висунуту кандидатуру проголосували 12 осіб, проти - 10, утрималися - 3. Скількома способами могло бути проведено таке голосування?

нехай М - Безліч студентів в групі, - безліч студентів, які проголосували за висунуту кандидатуру, - безліч студентів, які проголосували проти, - безліч студентів, тих, хто утримався від голосування. Тоді - впорядковане розбиття множини M. шукане число R(12, 10, 3) одно .?

Число розбиття вихідного безлічі M на k підмножин,, невпорядкованих між собою, обчислюється за формулою

,

а число всіх можливих розбиттів множини M на k підмножин, невпорядкованих між собою, так само

Приклад. Скількома способами з групи в 25 чоловік можна сформувати 5 коаліцій по 5 чоловік?

нехай X - Безліч людей в групі, - число коаліцій по i людина, де i= 1, ... 25. Тоді за умовами завдання, і, отже, шукане число дорівнюватиме

Теорема.нехай S (n, k) - Число розбиття безлічі n-X на k блоків. тоді обчислення S (n, k) може бути виконано рекурсивно на основі тотожностей: якщо, якщо n= 0 ,, якщо n> 0.

Доведення. Для доказу розглянемо безліч всіх розбиття n-X на k підмножин.

Це безліч можна уявити двома пересічними класами: тих розбиття, які містять одноелементний блок {n}, І тих, які його не містять. В цьому випадку n міститься принаймні в двоелементною блоці. Потужність першого класу дорівнює, т. Е. Така, яке число розбиття множини {1, 2, ...,n-1} На k-1 Блоків. Потужність другого класу дорівнює, оскільки кожному розбиття множини {1, 2, ...,n-1} На k-1 Блоків відповідає в цьому класі рівно k розбиття, утворених додаванням елемента n по черзі до кожного блоку. Доказ закінчено.

числа S (n, k) називаються числами Стірлінга другого роду. Розраховані за формулами (3.31) - (3.33), вони можуть бути представлені у вигляді трикутної таблиці - трикутника Стірлінга. Трикутник Стірлінга для значень n від 0 до 7 представлений в таблиці.Числа Стірлінга другого роду

n k
                     

числа Белла визначаються як сума всіх розбиття від 0 до n блоків безлічі n-X . (3.34)

Перші вісім чисел Белла в таблиці 3.2.

При за рахунками числа розбиття необхідно мати на увазі, що числа Белла ростуть дуже швидко. Так, наприклад, вже при n = 20 Bn = 51 724 158 235 372. числа Белла

n
Bn


Комбінаторні об'єкти дискретної математики. Алгоритмічні завдання комбінаторики. Завдання комівояжера. | розбиття чисел

Передача даних. | Локальні і глобальні змінні. | типи файлів | Процедури і функції | Об'єкт і клас. | Базові принципи ООП - інкапсуляція, поліморфізм і успадкування. | Поняття класу в мові ObjectPascal. Структура класу: поля, методи, властивості. | Конструктор і деструктор класу. | Поняття графа, методи опису графа, види графів. Ейлерови і Гамільтона графи. | Способи завдання графів |

© um.co.ua - учбові матеріали та реферати