Елементи комбінаторики:основні поняття і означення.

Усі процеси, що відбуваються у природі чи людському суспільстві, є наслідком взаємодії багатьох факторів. Для того щоб вивчити ці процеси і навчитися керувати ними, необхідно зיясувати, яку роль у досліджуваному процесі відіграє кожний фактор окремо. Щоб мати змогу застосувати математичні методи з метою вивчення взаємодії тих чи інших факторів, слід уміти виражати дію кожного з них кількісно. Щоб дістати потрібні числові дані, необхідно провести серію спостережень. Отже, спостереження найважливіша ланка будь-якого експерименту. Проте, слід відмітити, що кожне спостереження дає нам лише наслідок взаємодії основного фактора, який нас цікавить, з багатьма сторонніми, другорядними. За реальних умов під час дослідження будь-якого процесу застосовують метод його формалізації, беручи до уваги лише ті фактори, які істотно випливають на зазначений процес.

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

Означення: Множину називають упорядкованою, якщо при її побудові істотним є порядок розміщення елементів.

Означення: Переставленням із п елементів називають такі впорядковані множини з п елементів, які різняться між собою порядком їх розміщення.

Кількість таких упорядкованиїх множин обчислюється за формулою:

,

де п набуває лише цілих невід’ємних значень.

Означення: Розміщенням із п елементів по т називаються такі впорядковані множини, кожна із яких містить т елементів і які відрізняються між собою порядком розташування цих елементів або хоча б одним елементом.

Кількість таких множин обчислюється за формулою:

.

Означення: Комбінаціями з п елементів по т називаються такі множини з т елементів, які різняться між собою хоча б одним елементом.

Кількість таких множин:

.

Основний принцип комбінаторики(п равило добутку):

   Якщо деякий об’єкт А можна вибрати з сукупності об’єктів m різними способами, а для кожного з цих способів деякий другий вибір В можна здійснити n способами, то вибір А і В (у вказаному порядку) можна здійснити mn способами.

   Приклад 1. В їдальні для сніданку є m видів перших страв і n видів других страв. Скількома способами можна скласти в цій їдальні комплексний сніданок, що містить дві страви (першу і другу)?

   Розв’язування: Вибравши одну з m можливих страв, далі можна вибрати другу страву n способами. Тому загальне число можливих комплексних сніданків дорівнює mn.

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

   Якщо деякий об’єкт А можна вибрати з сукупності обיєктів m способами, а інший об’єкт В можна вибрати n способами, то вибрати або А,або В можна m + n способами.

   Приклад 2. У студентській групі налічується 25 студентів. Скількома способами можуть бути обрані в цій групі староста і профорг (обов’язки старости і профорга не можна виконувати один і той же студент)?

Розв’язування: Старостою може бути обраний один з 25 студентів. Після того, як обрано старосту профорга можна обрати серед 24 студентів. Отже, загальне число способів, якими можуть бути обрані староста і профорг, становить .

Вихідними в теорії ймовірностей є поняття стохастичного експерименту, випадкової події та ймовірності випадкової події.

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

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

  

 

Події та дії над ними.

У теорії ймовірностей під випробовуванням розуміють комплекс певних умов, відтворюваних як завгодно велику кількість разів, наявність якого веде до якого-небудь наслідку. Результат випробування називають подією або наслідком.

   Наприклад: підкидання монети – випробування, появи на ній “герба” – подія.

   Події позначають великими літерами латинської абетки А, В, С,....

   Означення: Подія, яка при кожному випробуванні обов’язково відбувається, називається вірогідною ( ).

     Означення: Подія, що не може відбутися при жодному випробуванні, називається неможливою (Ø).

   Означення: Подія називається протилежною до події А, якщо вона настає тільки тоді, коли не настає подія А.

   Означення: Сукупність подій утворює повну групу подій, якщо внаслідок випробування хоч одна з цих подій обов’язково відбудеться.

   Означення: Дві події називаються несумісними, якщо поява однієї з них виключає появу іншої.

   Серед усіх неможливих подій можна виділити множину так званих елементарних подій, що характеризуються такими ознаками:

1. Усі елементарні події взаємно виключають одна одну, і внаслідок випробування обов’язково відбувається одна з цих подій.

2. Яка б не була подія А, за елементарною подією, яка настала, можна робити висновок про те, настала чи не настала подія А.

Випадкові події поділяються на прості і складені.

Означення: Подія, що може відбутися внаслідок проведення однієї і лише однієї спроби (експерименту) називається простою випадковою подією.

Означення: Випадкова подія називається складеною, якщо її можна розкласти на прості події.

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

Операція над подіями.

Означення: Сумою (або обיєднанням) подій А і В називається подія, яка полягає в настанні події А, або події В.

Означення: Добутком (або перерізом) подій А і В називається подія, яка полягає в одночасному настанні як події А, так і події В.

Означення: Різницею подій А і В називається подія, яка полягає в тому, що настає подія А, але не настає подія В.

Властивості операцій.

       

3)

4)

5)

6)

7)

8)

9)

10)

11)

17) Закони де Моргана: .