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

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

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

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

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

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

,

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

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

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

.

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

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

.

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

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

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

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

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

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

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

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

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

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

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