Контрольная работа: Знаходження кусково-постійних конфігурацій множин

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

3. На множині натуральних чисел N визначимо відношення порядку за подільністю, тобто тоді і тільки тоді, коли a є дільником b. Таким чином ми отримаємо частково впорядковану множину. Наведені вище аксіоми справджуються тому, що будь-яке натуральне число є своїм дільником, два числа, які є дільниками одне одного, збігаються, і, нарешті, якщо a є дільником b, а b є дільником c, то a є дільником c. Ця множина не є лінійно впорядкованою, наприклад, жодне з чисел 2,3 не є дільником іншого. При цьому 1 є дільником будь-якого натурального числа, тому воно є найменшим елементом цієї частково упорядкованої множини.

4. Ланцюг з n елементів — це лінійно впорядкована множина з n елементів. У комбінаториці ланцюг, який складається з , позначається [n] або n.

5. Будь-яка множина A перетворюється на частково впорядковану множину, якщо визначити на неї таке відношення порядку: . У цьому разі можна порівняти два елементи A лише коли вони збігаються. Така частково впорядкована множина називається антиланцюгом.

6. Нехай A — це довільна множина, а Ω(A) — це множина, елементами якої є всі підмножини . Визначимо на Ω(A) частковий порядок за вмістком, тобто означає, що де B, C — дві підмножини в A. Тоді Ω(A) перетворюється на частково впорядковану множину з найменшим елементом порожньою множиною та найбільшим елементом A.

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

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

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

1. Теорію конфігурацій, що включає блок - схеми, групи підстановок, теорію кодування.

2. Теорію перерахування, що містить твірні функції, теореми обігу й вирахування кінцевих різниць.

3. Теорію порядку, що включає кінцеві впорядковані множини й ґрати, матриці й теореми існування, подібні до теорем Холу й Рамсея.

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

2.1 Теорія конфігурацій і теорія перерахування

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

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

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

Якщо елемент A можна вибрати m способами, а елемент B можна вибрати k способами, то вибір елемента A або B можна здійснити m + k способами.

Правило суми можна перефразувати теоретико-множинною мовою. Позначимо через | A | число елементів множини A, через - об'єднання множин A і B, через - декартовий добуток множин A і B. Тоді для непересічних множин A і B виконується рівність:

.

Узагальненням правила суми є правило добутку.

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

Якщо елемент A можна вибрати m способами, а після кожного вибору елемента A елемент B можна вибрати k способами, тоді, упорядковану пару елементів (A, B) можна вибрати m*k способами.

Правило добутку можна поширити на вибір послідовності (x1, x2, ..., x_n ) довільної кінцевої довжини n.

Теоретико-множинною мовою правило добутку формулюється так:

.

2.2 Блок-схеми

Комбінаторні конфігурації найбільш загального виду були досліджені в 30- е роки XX сторіччя й були названі блок-схемами (block desіgn). Блок-схеми складаються з наборів елементів, називаних блоками. Вибір елементів і пара елементів у блоки підкоряються певним правилам.

Урівноваженою неповною блок-схемою називається таке розміщення v різних елементів по b блоках, що кожний блок містить точно k різних елементів, кожний елемент з'являється точно в k різних блоках і кожна пара різних елементів a_i , a_j з'являється точно в блоках.

Множина всіх сполучень із v елементів по k, узятих як блоки, утворить повну блок-схему. Частина цих сполучень, у яких кожна пара a_i , a_j з'являється одне й те саме число раз, є неповною, але врівноваженою блок-схемою. Між п'ятьома параметрами блок-схеми виконуються наступні два співвідношення: