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

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Тема 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. Антикорупційні принципи

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