09.Комбінаторика(1)

1. Основні правила комбінаторики

2. Що таке комбінаторика

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

3.

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

4. Приклад

Задача. Скільки трицифрових чисел
можна записати за допомогою цифр 1,
2, 3, не повторюючи цифри в запису
числа ?
Розв’язання. Для першої цифри 3
варіанта, для другої – 2, а для третьої –
1. Всього: 3 ∙ 2 ∙ 1 = 6

5. Приклад

Задача. У трьох учнів виникла потреба
розподілити між собою 3 книжки.
Скількома способами можна це зробити ?
Розв’язання. 3 ∙ 2 ∙ 1 = 6

6. Приклад

Задача . У групі 21 студент. Скількома
способами можна вибрати трьох студентів
для проходження педагогічної практики в
трьох різних школах?
Розв’язання. 21 ∙ 20 ∙ 19 =7980

7. Комбінаторне правило додавання

Нехай n(A) – кількість елементів множини А,
а n(В) – кількість елементів множини В.
Якщо множини не мають спільних
елементів, то їх об'єднання А U В містить
n(A) + n(В) елементів, n(A U В) = n(A) +
n(В).
Якщо множини мають спільні елементи, то
вони ввійдуть у суму двічі. Тому:
n(A U В) = n(A) + n(В) – n(А∩В) .

8. Задача. Кожен учень класу – або дівчинка, або блондин, або любить математику. У класі 20 дівчаток, з них 12 блондинок, а одна

блондинка любить
математику. Всього у класі 24 учні-блондини,
математику з них люблять 12, а всього учнів (хлопчиків
та дівчаток), які люблять математику, 17, з них 6
дівчаток. Скільки учнів у цьому класі?
А – множина дівчаток, В – блондинів, С – учнів, які
люблять математику, то n(А U B U C) – шукане число.
А ∩ В – множина блондинок;
А ∩ С – множина дівчаток, які люблять математику ;
В ∩ С – множина всіх блондинів (хлопчиків та дівчаток), які
люблять математику ;
Тоді: n(А U B U C) = n(A) + n(В) + n(С) – n(А∩С) –
– n(А∩В) – n(В∩С) + n(А ∩ B ∩ C) = 20 + 24 +17 –
– ( 6 + 12 + 12) +1 = 32.

9. Перестановки (без повторень)

Будь-яка впорядкована множина, яка
складається з n елементів, називається
перестановкою з n елементів.
Число перестановок з n елементів
(позначається Pn) дорівнює добутку всіх
натуральних чисел від 1 до n, тобто n!

10. Приклад

Задача. Скількома способами можна
розставити на майданчику 6 волейболістів?
Розв’язання. Число способів розташування на
майданчику шести волейболістів дорівнює
числу перестановок із шести елементів:

11. Приклад

Задача. На полиці стоять 8 підручників. Скількома способами можна
поставити ці книжки на полицю так, щоб підручники з алгебри,
геометрії і фізики стояли поруч?
Розв’язання
Будемо розглядати підручники з алгебри, геометрії і фізики як одну
книжку. Тоді на полиці треба розмістити не 8 книжок, а 6. Це можна
зробити Р6 способами. Підручники з алгебри, геометрії і фізики
можна розмістити Р3 способами. Використовуючи правило
множення матимемо, що шукана кількість способів дорівнює
Відповідь: 4320.

12. Розміщення (без повторень)

Будь-яка впорядкована множина з m елементів даної
множини, яка містить n елементів, де m≤n,
називається розміщенням з n елементів
по m елементів.
Число розміщень з n елементів по m позначають
.
Число розміщень з n елементів по m дорівнює
добутку m послідовних натуральних чисел,
найбільшим із яких є n:
Якщо n=m, то
.

13. Комбінації (без повторень)

Будь-яка підмножина з m елементів даної множини, яка містить n
елементів, називається комбінацією з n елементів по m
елементів.
Число комбінацій з n елементів по m позначають символом
.
Число комбінацій з n елементів по m (1≤m≤n) дорівнює дробу,
чисельником якого є добуток m послідовних натуральних чисел,
найбільшим з яких є n, а знаменником – добуток m перших
послідовних натуральних чисел:
або

14. Трикутник Паскаля

Усі можливі значення (n=0,1,2,…, m=0,1,2,…,)
можна записати у вигляді трикутної таблиці.
Така таблиця називається трикутником
Паскаля.

15. Приклад

Задача. Скільки можна провести різних площин
через 5 точок простору, якщо ніякі чотири з
них не лежать в одній площині?
Розв’язання
Площина визначається трьома точками,
тому всіх площин буде
.
Відповідь: 10.

16. Приклад

Задача. У кошику лежать 8 різних яблук і 4 різні
груші. Треба вибрати 3 яблука і 2 груші.
Скількома способами це можна зробити?
Розв’язання
Вибрати 3 яблука з 8 можна способами.
Вибрати 2 груші із 4 можна способами. Тоді
за правилом добутку вибір потрібних фруктів
можна знайти
способами.
Відповідь: 336.

17. Біном Ньютона

Рівність
називають біномом Ньютона, або формулою
Ньютона.
Права частина рівності називається
біноміальним розкладом (у суму), або
розкладом бінома, а коефіцієнти –
біноміальними.

18. Приклад

Задача. Піднесіть до шостого степеня х-2у.
Розв’язання
Покладемо а=х, b=-2у, тоді отримаємо

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

Подія – це явище, про яке можна сказати, що воно відбувається
або не відбувається за певних умов. Події позначаються
великими літерами латинського алфавіту: А, В, С,… Будь-яка
подія відбувається внаслідок випробування (експерименту,
досліду).
Випробування – це умови, за яких відбувається (чи не
відбувається) подія.
Події розподіляються на випадкові, вірогідні та неможливі.
Випадковою називається подія, яка може відбутися або не
відбутися внаслідок певного випробування.
Вірогідною називається подія, яка внаслідок даного
випробування обов’язково відбудеться.
Неможливою називається подія, яка внаслідок даного
випробування не може відбутися.

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

Теорія ймовірностей – розділ математики, що вивчає
закономірності випадкових подій.
Попарно несумісні події – це події, кожні дві з яких не можуть
відбутися одночасно.
Рівноможливі події – події, кожна з яких не має ніяких переваг,
щоб з’являтися частіше за іншу під час багаторазових
випробувань, що проводяться за однакових умов.
Повною групою подій називається множина таких подій, коли
в результаті кожного випробування обов’язково має відбутися
хоча б одна з них.
Якщо події мають властивості: 1) утворювати повну групу
подій; 2) бути несумісними; 3) бути рівно можливими, то такі
події утворюють множину, яка називається простором
елементарних подій.

21. Класичне означення ймовірності

Відношення числа m елементарних подій, які сприяють
події А, до загальної кількості n подій простору
називається ймовірністю випадкової події А і
позначається Р(А), тобто
,
де m – число подій, які сприяють події А, n – число подій
простору елементарних подій (0≤m≤n).
Імовірність вірогідної події дорівнює 1, імовірність
неможливої події дорівнює 0, а ймовірність Р(А)
випадкової події А задовольняє умову 0<Р(А)<1.

22. Приклад

Імовірність того, що при киданні двох
монет випаде два герби, дорівнює 1/4 ,
бо простір елементарних подій такий:
А1 – випали два герби; А2 – випали
герб і число; А3 – випали число і герб;
А4 – випали два числа, а шуканій події
сприяє лише одна подія – А1.

23. Статистичне означення ймовірності

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

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

Сумою двох подій А і В називається подія , що
полягає у здійсненні під час одиничного
випробування або події А, або події В, або
обох подій А і В одночасно (позначається
С=А+В, або
).
Подія
називається протилежною події А,
якщо вона відбувається тоді і тільки тоді, коли
подія А не відбувається.
Добутком двох подій А і В називається
подія С, яка полягає в одночасному здійсненні
обох подій А і В під час одиничного
випробування (позначається
або
).

25. Теорема про ймовірність суми подій

Імовірність суми двох несумісних подій А і В
дорівнює сумі ймовірностей цих подій. Якщо
, то Р(А+В)=Р(А)+Р(В).
Наслідок 1. Сума ймовірностей подій
А1,А2,…,An, які утворюють повну групу і
попарно несумісні, дорівнює 1
Р(А1)+Р(А2)+…+Р(Аn)=1.
Наслідок 2. Сума ймовірностей протилежних
подій дорівнює 1

26. Теорема про ймовірність добутку подій

Дві події називаються незалежними, якщо
ймовірність появи однієї з них не залежить від
того, відбулася інша подія чи ні.
Імовірність добутку двох незалежних
подій А і В дорівнює добутку ймовірностей
цих подій, тобто
.
Якщо подія А1, А2, …Аn незалежні, то
ймовірність здійснення принаймні однієї з них
С може бути виражена через імовірність цих
подій формулою

27. Незалежні випробування. Схема Бернуллі

Взаємно незалежними випробуваннями називаються такі
випробування, у яких імовірність результату кожного з них не
залежить від того, які результати має чи матиме решта
випробувань.
Багато задач у теорії ймовірностей зводяться до такої схеми, яка
називається схемою Бернуллі: відбувається n незалежних
випробувань, у кожному з яких подія А може настати чи не
настати. Імовірність того, що випадкова подія А в кожному
випробуванні відбувається, однакова і дорівнює p, а ймовірність
того, що не відбувається, q=1-p. Треба знайти Рm,n того, що
подія А настане m разів у цих n випробуваннях. Шукану
ймовірність можна обчислити за формулою Бернуллі

28. Приклад

Задача. У скрині лежать 20 кульок, із яких 12 білих, решта чорні.
Виймають навмання 2 кульки. Яка ймовірність того, що вони
будуть білі?
Розв’язання
Загальна кількість елементарних подій випробування (вийнято 2
кульки) дорівнює числу способів, якими можна вийняти 2 кульки
із 20, тобто числу комбінацій із 20 елементів по 2 (
).
Обчислимо кількість елементарних подій, які сприяють події
«вийнято 2 білих кульки». Ця кількість дорівнює числу способів,
якими можна вийняти 2 кульки із 12 білих, тобто числу
комбінацій із 12 елементів по 2 (
).
Отже, якщо подія А – «вийнято 2 білі кульки», то

29. Приклад

Задача. У скрині лежать 2 чорних, 3 червоних, 9 зелених, 6 синіх
кульок. Виймають навмання 1 кульку. Яка ймовірність того, що
вона не чорна?
Розв’язання
Нехай подія А – «поява нечорної кульки»; А1 – «поява чорної
кульки»; А2 – «поява червоної кульки»; А3 – «поява зеленої
кульки»; А4 – «поява синьої кульки». Тоді А=А2+А3+А4, причому
А2, А3, А4 – несумісні,
За теоремою ймовірностей суми несумісних подій отримуємо

30. Приклад

Задача. Два мисливці стріляють одночасно і незалежно
один від одного по мішені. Імовірність влучень у
мішень відповідно дорівнюють 0,7 і 0,8. Знайдіть
імовірність того, що обидва мисливці влучать у ціль.
Розв’язання
Подія А – «перший мисливець влучив у ціль»,
Р(А)=0,7.
Подія В – «другий мисливець влучив у ціль»,
Р(В)=0,8.
Подія С=А∙В – «обидва мисливці влучили у ціль»,
тоді