• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Тема 1. Основні поняття та принципи комбінаторики

Коротка історична довідка

Перші роботи, в яких виникли основні поняття теорії імовірностей, з'явились у XV - XVI століттях як спроба побудови теорії азартних ігор і належать таким видатним ученим, як Б. Спіноза, Дж. Кардано, Галілео Галілей.

Слідуючий етап (кінець XVII - початок XVIII сторіч) розвитку теорії імовірностей пов'язаний з роботами Б.Паскаля, П.Ферма, X.Гюйгенса, К.Гаусса, Я.Бернуллі та Н.Бернуллі, С.Пуассона, А.Муавра, П.Лапласа, Т.Байєса.

Я.Бернуллі зробив перші теоретичні обгрунтування накопичених раніше фактів.

В XIX сторіччі теорію імовірностей почали успішно застосовувати у страховій справі, артилерії, статистиці.

Лише наприкінці XIX сторіччя П.Л. Чебишов та його учні А.А. Марков та A.M. Ляпунов перетворили теорію імовірностей у математичну науку.

Подальшим розвитком теорії імовірностей та випадкових процесів зобов' язані таким математикам, як С.Н. Бер-штейн, A.M. Колмгогоров, Б.В. Гніденко, А.В. Скороход, B.C. Королюк, Ю. Нейман, І.I. Гіхман, І.М. Коваленко.

Часто для знаходження чисел m та n, що входять у класичне означення імовірності події, потрібно знати кількість різноманітних сполук, які можна одержати з n елементарних наслідків.

Класифікація та властивості таких сполук, а також формули для обчислення кількості різних сполук розроблені математиками і містяться у розділі "Комбінаторика" курсу алгебри.

Ознайомимось із основними поняттями та формулами комбінаторики.

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

Приклад 1. Із цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 можна скласти багато різних сполук по 2, 3, 4, ..., цифр. Деякі з них будуть відрізнятися кількістю цифр, а деякі відрізнятимуться лише порядком цифр. Наприклад123, 8056, 96, 312, 123, 231, 321.

Усі можливі сполуки доцільно класифікувати. Сполуки бувають трьох видів:

· перестановки;

· розміщення;

· сполучення.

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

Кількість перестановок з n елементів позначають Р_n і знаходять за формулою

(1.1)

Позначення n! вимовляють "n факторіал".

За означенням 0! = 1.

Приклад 2. Скільки п'ятизначних чисел можна записати, використовуючи п'ять різних цифр (крім нуля)?

Розв’язання. Сполуки, що утворюють з п'яти різних цифр п'ятизначні числа, можуть відрізнятися лише порядком цифр, тому такі сполуки будуть перестановками з 5 елементів. Згідно формули (1.1) їх кількість буде

Р₅ = 5! = l∙2∙3∙4∙5 = 120.

Означення 3. Розміщенням з п елементів по т називають такі комбінації, які складаються з т елементів, взятих з даних п елементів (т < п) і відрізняються як порядком, так і елементами.

Кількість розміщень з n елементів по m позначають і знаходять за формулою

(1.2)

Приклад 3. Студенти другого курсу згідно учбового плану вивчають 10 дисциплін. На один день можна планувати заняття з 4 дисциплін. Скількома способами можна скласти розклад занять на один день?

Розв’язання. Усі можливі розклади занять на один день - це сполуки з 10 по 4, які можуть відрізнятися дисциплінами або їх порядком, тобто ці сполуки -розміщення. Кількість таких розміщень згідно формули (1.2) буде

= 10 ∙ 9∙ 8 ∙ 7 = 5040.

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

Кількість сполучень з n елементів по m позначають і знаходять за формулою

Зауваження 1. Перестановки можна розглядати як частковий випадок розміщень

Між кількістю перестановок, розміщень та сполучень існує простий зв'язок

Часто доцільно використовувати такі властивості сполучень:

a) ;

б);

в) ;

г) .

Приклад 4. У ящику 10 виробів, з яких 2 нестандартні. Навмання беруть 6 виробів. Яка імовірність того, що усі взяті вироби будуть стандартними?

Розв’язання. Позначимо подію А - взято 6 стандартних виробів. Згідно умови задачі, немає значення, в якому порядку беруть 6 виробів, тобто це будуть сполучення.

Тому кількість усіх можливих елементарних наслідків буде.

Події А сприяють лише сполуки по 6 виробів з 8 стандартних у будь-якому порядку, тобто

Отже згідно класичному означенню імовірності події А маємо

Тепер ознайомимось з основними принципами комбінаторики.

Принцип суми. Якщо множина А містить п елементів, а множина В містить т елементів і А ∩ В = 0, тоді множина A U В містить п + т елементів.

Доведення. Здійснюється простим рахуванням елементів множини AUВ.

Спочатку рахуємо усі елементи множини А. Вони одержать номери від 1 до n. Серед них немає елементів множини В, тому що А ∩ В = 0.

Тепер будемо рахувати елементи множини B. Вони одержать номери від n + 1 до n + m, поскільки множина В за умовою має m елементів.

Таким рахуванням усі елементи множини A U В будуть вичерпані. Вони одержать номери від 1 до n + m, тому A U В містить n + m елементів.

Зауваження 2. Принцип суми має місце для суми k множин, тобто для

A₁UA₂U…UA_k=

Принцип добутку. Якщо множина А містить п елементів, а множина В містить т елементів) то множина С усіх можливих пар (a_i,b_k) (і 1,2, ...,n; k = 1, 2, . . . , т) містить п·т елементів.

Доведення. Множину С розіб'ємо на підмножини

C₁={(a₁,b_k), k=1,2,…,m};

C₂={(a₂,b_k), k=1,2,…,m};

………..

C_i={(a_i,b_k), k=1,2,…,m};

……….

C_n={(a_n,b_k), k=1,2,…,m};

Оскільки C₁ складається лише з пар, що містять a₁, а множина C₂ складається лише з пар, що містять a₂, то C₁∩ C₂ = 0.

Аналогічно одержуємо, що C_i∩ C_j = 0, коли i≠ j.

Тепер доведемо, що

Дійсно, нехай (a_i,b_k) будь-яка пара. Вона входить в С згідно визначенню множини С. Вона також входить і в множину C_i тому, що (a_i,b_k) Є C_i. Кожна підмножина C_i множини С містить m елементів, тому згідно визначенню принципу суми число елементів у їх об'єднанні дорівнює m·n.

Читайте також:

1. II. Основні закономірності ходу і розгалуження судин великого і малого кіл кровообігу
2. II. Поняття соціального процесу.
3. V. Поняття та ознаки (характеристики) злочинності
4. А/. Поняття про судовий процес.
5. Аграрна політика як складова економічної політики держави. Сут­ність і принципи аграрної політики
6. Адвокатура в Україні: основні завдання і функції
7. Адміністративний проступок: поняття, ознаки, види.
8. Адміністративні провадження: поняття, класифікація, стадії
9. Акти застосування юридичних норм: поняття, ознаки, види.
10. Амортизація основних засобів, основні методи амортизації
11. Аналіз ступеня вільності механізму. Наведемо визначення механізму, враховуючи нові поняття.
12. Антикорупційні принципи

Переглядів: 1768