Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
архив прош.сесий / Lektsiya_18_Kombinatorika_Teoremi_TJ_Nadiynist.doc
Скачиваний:
11
Добавлен:
19.02.2016
Размер:
398.85 Кб
Скачать

18

Л Е К Ц І Я № 18

з навчальної дисципліни Основи вищої математики та теорії ймовірностей

напряму підготовки ”Соціологія”

освітньо-кваліфікаційного рівня бакалавр

спеціальності _____________________________________________________

Лекцію розроблено доцентом кафедри ВМ ДУІКТ (2011р) Омецінською О.Б.

Тема: Основні поняття комбінаторики, застосування до розв’язання задач теорії імовірностей. Основні теореми теорії ймовірностей. Розрахунок надійності простих систем

Основний зміст

1. Комбінаторика: правило підрахунку числа елементів суми 2-х множин; основне правило комбінаторики; переставлення, сполучення, розміщення, із різних елементів та з повторенням. Застосування комбінаторики до розв’язання задач теорії імовірностей.

2. Основні теореми теорії ймовірностей:

2.1. Умовна ймовірність, формула обчислення та властивості. Незалежність випадкових подій. Теореми про ймовірність суміщення випадкових подій.

2.2. Теорема про ймовірність суми 2-х сумісних подій.

3. Застосування теорем теорії ймовірностей до розрахунку надійності простих систем.

Текст лекції

1. Комбінаторика: правило підрахунку числа елементів суми 2-х множин; правило множення; переставлення, сполучення, розміщення, із різних елементів та з повторенням. Застосування комбінаторики до розв’язання задач теорії імовірностей

Щоб обчислити ймовірність випадкової події А за формулою класичної ймовірності для випробувань, елементарні події в яких є дискретною (зліченною) скінченною множиною рівноможливих подій,

, (1)

потрібно знайти кількість n всіх елементарних подій у множині простору  даного випробування, а також кількість їх m у підмножині, яка відповідає події А. Для цього часто застосовують формули комбінаторики – одного з розділів дискретної математики, що набув важливого значення в зв’язку з його використанням в теорії ймовірностей, математичній логіці, теорії чисел, обчислювальній техніці, кібернетиці, теорії передачі дискретної інформації тощо.

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

Комбінаторика є теорією скінченних множин.

Нехай серед елементів множини G немає таких, що повторюються, і загальна кількість її елементів рівна n=N(G) (n-елементна множина різних елементів).

Правило підрахунку кількості елементів суми множин А і В:

, (2)

отже, у випадку спільних елементів, , із загальної суми елементівN(А)+N(В) вони вилучаються, оскільки в неї ввійшли двічі. Якщо множини А і В не мають спільних елементів, тобто , остання складова в (2) відсутня.

Основне правило комбінаторики (правило множення)

Нехай потрібно виконати k дій. Якщо першу дію можна виконати n1 способами, другу дію – n2 способами і так до k-тої дії, то всі k дій разом можуть бути виконаними кількістю способів, рівним числу

n=n1n2n3nk. (3)

Існує низка задач, в яких для обчислення величин n і m у формулі (1) класичної ймовірності застосовують елементи комбінаторики: переставлення, розміщення та сполучення.

І. Переставлення

Дамо допоміжне поняття: добуток із всіх натуральних чисел від 1 до n називають „n факторіал” і позначають: Будемо вважати, що 0!=1, 1!=1.

Означення 1. n-елементну множину називають упорядкованою, якщо кожному її елементу поставлено у відповідність натуральне число (номер елемента) від 1 до n. У протилежному випадку множина – невпорядкована.

Кількість Pn переставлень із n різних елементів

Множину, що містить n різних елементів, упорядкуємо, пронумерувавши всі її елементи.

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

Формула підрахунку кількості Пn різних способів, якими можна упорядкувати n-елементну множину, безпосередньо випливає із основного правила комбінаторики, (3): якщо перше місце надати одному із n елементів, то 2-е місце можна надати одному із всіх інших (n-1) елементів і таких переставлень буде (n-1), 3-тє місце – одному із всіх інших (n-2) елементів і таких переставлень буде (n-1)∙(n-2), і т.д., – загальна кількість усіх переставлень буде (n-1)∙(n-2)∙(n-3)2. Але перше місце можна було надати не одному, а будь-якому із n елементів, тому для кількості переставлень із n різних елементів маємо формулу

Пn=n∙(n-1)∙(n-2)∙(n-3)2∙1=n! (4)

Приклад 1. На кожній із шести карток розрізної абетки записано одну з літер Я, І, Р, Е, О, Т.

Яка ймовірність того, що картки, навмання розкладені в рядок, утворять слово ТЕОРІЯ ?

 Кількість усіх елементарних рівноможливих подій даного випробування (елементів множини Ω) – число переставлень із 6-ти різних елементів: n=6!=6 5 4 3 2 1=720,

Лише одна з цих подій сприяє появі слова ТЕОРІЯ, m=1. Позначивши розглядувану подію через А, для її ймовірності дістанемо:

P(А)=m/n=1/720. 

Приклад 2. Знайти ймовірність події А, яка полягає в тому, що двійко певних осіб виявляться поруч при випадковому розміщенні 8-ми гостей на 8-ми місцях за столом, що має форму: 1) прямолінійного стояка; 2) круга.

 Множина Ω простору всіх елементарних рівноможливих подій даного випробування – переставлення із 8-ми різних елементів, їхня кількість n=П8=8! Виділимо із них ті m переставлень, що сприяють події А – розміщенню поруч двох певних осіб:

1) за розміщення на сидіннях вздовж прямолінійного стояка їхня кількість дорівнює числу П7 переставлень із 7-ми елементів (оскільки два фіксовані елементи із 8-ми переставляються разом), збільшеного вдвічі, адже в усіх П7 переставленнях два фіксовані елементи можуть помінятися місцями між собою; отже m=2П7, і для ймовірності події А дістанемо:

P(А)=m/n=2П7/П8=2∙7!/8!=2/8=0,25;

2) за розміщення на сидіннях за круглим столом m=2П7+2П6, в чому неважко переконатись, уявивши, що попередній стояк “замикається сам на собі” в круглий стіл, тоді підраховане в попередній задачі число m=2П7 слід збільшити на кількість П6 переставлень, в яких дві фіксовані особи розміщено на різних кінцях стояка, збільшивши це чисто вдвічі, адже ці особи можуть помінятися місцями між собою; для ймовірності події А дістанемо:

P(А)=m/n=(2П7+2П6)/П8=2∙(7!+6!)/8!=2∙6!(7+1)/8!=2∙(7+1)/(7∙8)=2/7.

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

Кількість переставлень із повторенням елементів

Кількість способів, якими можна упорядкувати n-елементну множину, в котрій k1 елементів належить типу В1 (або елемент В1 повторюється k1 разів), k2 елементів – типу В2, , km елементів – типу Вm, обчислюється за формулою

; k1+k2++km=n. (41)

Доказ цієї формули очевидний, якщо скористатися формулою (4) для числа переставлень із n різних елементів та правила множення (3), уявивши, що в множині переставлень із n елементів повторювані елементи стають різними і їх також можна переставляти: елементи типу В1k1! способами, елементи типу В2k2! способами , елементи типу Вmkm! способами. Тоді маємо , звідки випливає (41).

Приклад 3. Із літер розрізного алфавіту було складено слово «АНАНАС», і після цього ці літери кинуто в скриньку і ретельно перемішано. Знайти ймовірність того, що, беручи літери одну за одною й укладаючи їх підряд, знову дістанемо це слово.

 Позначимо через В подію, що полягає в появі слова «АНАНАС».

Підрахуємо кількість всіх елементарних подій випробування за формулою (41) для переставлень з повтореннями, позначивши в ній величину n через nп=6, k1=3 (число повторень літери А), k2=2 (число повторень літери Н), k3=1 (літера С не повторюється), k1+k2+k3=nп=6. Отже, для кількості n всіх елементарних подій дістанемо

n=6!/(3!∙2!∙1!)=720/(6∙2∙1)=60.

Всі переставлення з n елементів з повтореннями серед них фіксованої кількості елементів одного типу є рівноможливими елементарними подіями випробування. Адже, поява слова АНАНАС чи іншого слова-переставлення, скажімо НАНААС, із набором одних і тих самих 6-ти літер, – рівноможливі події. Лише одне із цих переставлень сприяє події В, m=1. Отже, маємо P(В)=m/n=1/60≈0,0167. 

Зауваження 1. Задачу можна розв’язати в інший спосіб, виокремивши кожну із 6-ти літер – надавши їм у відповідність числа-номери від 1 до 6 (для більш наглядного виділення рівноможливих елементарних подій випробування). Тоді кількість всіх рівноможливих елементарних подій випробування дорівнюваниме числу переставлень із 6-ти різних елементів і обчислюватиметься за формулою переставлень (4), n=6!=720. Із них сприятиме події В (появі слова АНАНАС) кількість переставлень, з урахуванням можливого переставлення: 3-х номерів, що відповідають літері А; 2-х номерів, що відповідають літері Н. За основним правилом комбінаторики дістанемо: m=3!2!=12. Отже, P(В)=m/n=12/720=1/60.

Соседние файлы в папке архив прош.сесий