Розділ 1.     Методи квантитативної лінґвістики

1. 1.Комбінаторний аналіз

План викладення матеріалу

1.1.1. Множина. Кортеж. Декартів добуток

1.1.2. Операції над множинами. Доведення рівностей з множинами

1.1.3. Взаємно однозначна відповідність

1.1.4. Основні правила комбінаторики. Розміщення і сполучення

1.1.5. Обчислення кількості розміщень і сполучень

1.1.6. Перестановки

1.1.7. Задача про цілочислові розв’язки

1.1.8. Розв’язування комбінаторних задач

1.1.9. Контрольні питання

1.1.10. Тести для самоконтролю

1.1.11. Задачі для самостійної роботи

Термін «комбінаторика» походить від латинського слова «combina», що українською означає – «поєднувати», «об’єднувати». Комбінаторика – це розділ математики, присвячений розв’язуванню задач вибору і розташування елементів відповідно до певних заданих вимог із використанням різного роду комбінацій, які можна утворити з елементів певної скінченної множини [83-86], [95, с. 110]. Схему зв’язків комбінаторики та розділів квантитативної лінґвістики в межах цього видання наведено на рис. 1.1. Методи комбінаторного аналізу, які використовують у лінґвістичних дослідженнях, застосовують у процесі ймовірнісного моделювання тексту для вивчення функціонування мови та мовлення. Знання комбінаторики особливо необхідні під час реалізації алгоритмів машинного послівного перекладу й інформаційного пошуку, а також для обчислення формально-структурних характеристик інформації, для оцінювання «гнучкості мови» [95, с.137]. Використання методів комбінаторики закладене в лінґвістичних схемах розв’язування задач криптології. Комбінаторні методи є в основі розв’язування багатьох задач теорії ймовірностей та пов’язаних з нею наукових напрямів.

1. 1.1.Множина. Кортеж. Декартів добуток

Теорія множин, основи якої викладено тут, відома в математиці під назвою наївної теорії множин. Є й інші варіанти побудови теорії множин, наприклад, конструктивний і формалістський, у яких поняття множини вводять інакше (у конструктивній теорії множин поняття множини означають). У нас поняття множини первісне, тобто неозначуване. Опишемо це поняття так: множиною називають будь-яке зібрання визначених і відмінних один від одного об’єктів нашої інтуїції або інтелекту, яке уявляють як єдине ціле. Відповідно до цього опису увагу переносять з окремих об’єктів на сукупності, які розглядають як деякі цілісні утворення.

У математиці застосовують такі синоніми терміну «множина»: система, сукупність, клас, область.

Об’єкти, які утворюють множину, називають її елементами. Про множину говорять, що вона містить ці елементи. Якщо об’єкт a є елементом множини A, то пишуть aÎA; в протилежному випадку aÏA.

Множину можна задати переліченням її елементів у фігурних дужках. Наприклад, множина A={a, e, i, o, u} містить елементи a, e, i, o, u й лише ці елементи. Множина не може містити двох однакових елементів, а порядок її елементів не фіксують.

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

Таблиця 1.1

Спеціальні позначення для часто використовуваних множин

Задати множину можна, зазначивши спільну властивість усіх її елементів. Тоді множину A задають за допомогою позначення A={x | P(x)}, яке читають так: «A – це множина об’єктів x, які мають властивість P(x)». Наприклад, A={x | xÎN₀, x<7} – це множина {0, 1, 2, 3, 4, 5, 6}. Іноді замість вертикальної риски використовують дві крапки, тобто пишуть A={x : xÎN₀, x<7}.

Дві множини A та B називають рівними, якщо вони складаються з одних і тих самих елементів. Рівність множин A та B записують як A=B.

Множину A називають підмножиною множини B, якщо кожний елемент множини A належить множині B. У такому разі пишуть AÌB, причому це не виключає, що A=B. Якщо A=B або A=Æ, то A називають невласною підмножиною множини B. Якщо A¹B і A¹Æ, то A називають власною підмножиною множини B. Для будь-якої множини A правдиве включення ÆÌA.

Зазначимо, що в літературі іноді використовують позначення AÍB; тоді позначення AÌB резервують для випадку, коли AÍB і A¹B.

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

Часто всі розглядувані в певній ситуації множини являють собою підмножини якоїсь множини, яку називають універсальною множиною або універсумом. Універсальну множину позначають як U.

Для заданої множини A можна розглянути множину всіх її підмножин, включно з порожньою множиною Æ і самою множиною A. Цю множину позначають 2^A чи P(A) й називають множиною-степенем, або булеаном множини A. Для скінченної множини A множина 2^A містить 2^|A| елементів.

Задача 1.1. Нехай A={0, 1, 2}. Знайти булеан множини A.

Розв’язок. 2^A={Æ, {0}, {1}, {2}, {0,1}, {0,2}{1,2}, {0,1,2}}. Ця множина містить 2³ = 8 елементів.

Кортеж – це впорядкований набір елементів. Сказане не слід розглядати як означення кортежу, оскільки тоді потрібно дати пояснення з приводу його синоніма «впорядкований набір». Поняття «кортеж» (синоніми – вектор, рядок, ланцюжок) уважатимемо, як і поняття множини, первісним, тобто неозначуваним. Елементи, що утворюють кортеж, називають його компонентами. Компоненти нумерують, кількість компонент називають довжиною або розмірністю кортежу. Нескінченні кортежі не розглядатимемо.

На відміну від елементів множини, компоненти кортежу можуть повторюватись. Кортеж записують у круглих дужках, наприклад (a, b, c, a, d) – кортеж довжиною 5. Іноді дужки й навіть коми не пишуть, наприклад кортеж 011001. Кортежі довжиною 2 часто називають парами, довжиною 3 – трійками. Кортежі довжиною n іноді називають n-ками («енками»).

Два кортежі рівні, якщо вони мають однакову довжину та відповідні їх компоненти рівні. Іншими словами, кортежі (a₁, …, a_m) та (b₁, …, b_n) рівні, якщо m=n та a₁=b₁, a₂=b₂, …, a_m=b_n.

Декартовим добутком множин A та B (позначають A´B) називають множину всіх пар (a, b) таких, що aÎA, bÎB. Зокрема, якщо A=B, то обидві компоненти належать A. Такий добуток позначають як A² та називають декартовим квадратом множини A. Аналогічно, декартовим добутком n множин A₁, …, A_n (позначають A₁´…´A_n) називають множину всіх кортежів (a₁, …, a_n) довжиною n таких, що a₁ÎA₁, …, a_nÎA_n. Частковий випадок A´…´A позначають як Aⁿ і називають n-м степенем множини A.

Задача 1.2. Нехай A={1, 2}, B={a, b, c}. Знайти A´B та B´A.

Розв’язок. Скориставшись означенням декартового добутку, одержимо A´B={(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)}, B´A={(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)}.

Зрозуміло, що загалом A´B≠B´A.

Для скінченних множин потужність (кількість елементів) декартового добутку дорівнює добутку потужностей цих множин: |A´B|=|A|×|B|.

1. 1.2.Операції над множинами. Доведення рівностей з множинами

Будемо вважати, що всі розглядувані множини є підмножинами деякого універсума U. Для довільних множин A та B можна побудувати нові множини за допомогою теоретико-множинних операцій, поданих в табл. 1.2.

Таблиця 1.2

Теоретико-множинні операції

(Для ознайомлення з повним текстом статті необхідно залогінитись)