- •Т е о р і я й м о в і р н о с т е й т а
- •03056, Київ-56, просп. Перемоги, 37 Зміст
- •1. Елементи комбінаторики
- •2. Біноміальні тотожності
- •3. Формула включень та виключень
- •4. Класичне означення ймовірності
- •5. Геометричний метод знаходження ймовірності
- •6. Умовні ймовірності, незалежні події, формула повної ймовірності, формула Байєса
- •Дискретні випадкові величини, математичне сподівання та дисперсія
- •Загальне поняття випадкової величини, функції від випадкових величин
- •Граничні теореми
- •0.74 1.12 3.75 4.33 5.71 6.09 7.89 8.03 9.55 10.22.
- •Список використаної літератури
2. Біноміальні тотожності
Біноміальні коефіцієнти мають ряд важливих властивостей, які можна подати у вигляді тотожностей. Серед найбільш поширених наведемо такі:
; (8)
; (9)
; (10)
(11)
Тотожність (8) випливає безпосередньо з означення (формула (2)). Рівності (10) та (11) є наслідками бінома Ньютона (формула (3)), якщо покласти тавідповідно. Співвідношення (9) легко доводиться аналітично з використанням означення . В той же час більш цікавим є доведення, що ґрунтується на комбінаторних міркуваннях. Дійсно,– це кількість способів, якими середрізних предметів можна обрати підмножину зпредметів. Візьмемо конкретний предмет. Існує дві можливості: або цей предмет міститься у підмножині зпредметів, або ні. У першому випадку потрібно додатково вибратипредмет з, що залишились (кількість таких комбінацій дорівнює). У другому випадкупредметів потрібно вибрати з(кількість комбінацій дорівнює). Оскільки множини комбінацій, що відповідають першому та другому випадкам, не перетинаються, то за правилом додавання отримуємо формулу (9).
У багатьох випадках біноміальні тотожності занадто складно доводити аналітично, ґрунтуючись на означенні . В той же час комбінаторні або геометричні міркування дозволяють це зробити набагато простіше. В основу доведення покладено такий принцип: одну й ту ж саму задачу розв’язують двома способами, один з яких ґрунтується на безпосередньому використанні комбінаторної формули, в результаті чого отримують просту відповідь, а другий – розбиває розв’язання задачі на декілька кроків, що призводить до відповіді у вигляді деякої суми. Розглянемо три приклади.
Приклад 1 (аналітичний метод). Довести тотожність
(12)
Доведення. Співвідношення (12) випливає безпосередньо з бінома Ньютона (формула (3)). Дійсно, враховуючи те, що
маємо
Приклад 2 (комбінаторний метод). Довести тотожність
(13)
де у випадку
Доведення. Нехай – це всі-елементні підмножини множини
Очевидно, що їх кількість визначається правою частиною рівності (13). Позначимо Розіб’ємонамножину, що не перетинаються, а саме,містить всі ті-елементні підмножини з, у яких рівноелементів належатьтаелементів належать(якщоабо, то– пуста множина). Кількість-елементних підмножин здорівнює. Аналогічно, кількість-елементних підмножин здорівнює. Оскільки кожну-елементну підмножину зможна доповнити будь-якою-елементною підмножиною з, то за правилом множення множинаміститьпідмножин. Множинине перетинаються. Тому за правилом додавання множинамістить кількість елементів, що визначається лівою частиною рівності (13).
Приклад 3 (геометричний метод). Довести тотожність
(14)
де
Доведення. Розглянемо всі найкоротші шляхи, що ведуть з точки у точку(рис. 1).Очевидно, що загальна кількість усіх таких шляхів дорівнює . Розіб’ємо всі мінімальні шляхи на множиниза принципом: шлях належить , якщо він перетинає пряму у точці. Кожен шлях з складається з трьох частин: шлях з точкиу точку, горизонтальний відрізок, що з’єднує точкиі, та шлях з точкиу точку. Таким чином, загальна кількість шляхів у множинідорівнює . Оскільки множинине перетинаються, то за правилом додавання отримуємо ліву частину формули (14).
Рис. 1.