топологічна комбінаторика
Аналоги комбінаторних концепцій і методів використовуються і в топології, при вивченні дерева прийняття рішень, частково впорядкованих множин, розмальовок графа і ін.
25) Що називають перестановками?
Перестановки - різні впорядковані множини, які відрізняються лише порядком елементів (тобто можуть бути отримані з того ж самого безлічі).
26) За якою формулою обчислюють число перестановок з n різних елементів?
Перестановки. Візьмемо n різних елементів: a1, a2, a3, ..., an. Будемо переставляти їх усіма можливими способами, зберігаючи їх кількість і змінюючи лише порядок їхнього розташування. Кожна з отриманих таким чином комбінацій називаетсяперестановкой. Загальна кількість перестановок з n елементів позначається Pn. Це число дорівнює добутку всіх цілих чисел від 1 до n:
Символ n. (Називається факторіал) - скорочений запис твору: 1 · 2 · 3 · ... · (n - 1) · n.
П р и м і р. Знайти число перестановок з трьох елементів: a. b. c.
Р і ш е н і е. Відповідно до наведеної формулою: P3 = 1 · 2 · 3 = 6.
Дійсно, ми маємо 6 перестановок: abc, acb, bac, bca, cab, cba.
27) Що називають розміщеннями? Запишіть формулу, за якою обчислюють число розміщень з n елементів по m.
Розміщення - це упрядоченние підмножини даного кінцевого безлічі.
Розміщення. Будемо складати групи з m різних елементів, взятих з безлічі, що складається з n елементів, маючи в своєму розпорядженні ці m взятих елементів в різному порядку. Отримані комбінації називаються розміщеннями з n елементів по m.
Їх загальна кількість позначається: і дорівнює добутку:
П р и м і р. Знайти число розміщень з чотирьох елементів a, b, c, d по два.
Р і ш е н і е. Відповідно до формули отримаємо:
Ось ці розміщення: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.
28) Що називають поєднаннями? Запишіть формулу, за якою обчислюють число поєднань з n елементів по m.
Поєднання без повторень з n елементів по m є m -елементное підмножина деякого n -елементного безлічі.
Коротко такі поєднання називають "поєднання з m по n" і їх число позначають або. Далі n -елементное безліч будемо позначати як n-безліч.
Сполучення. Будемо складати групи з m різних елементів, взятих з безлічі, що складається з n елементів, не беручи до уваги порядок розташування цих m елементів. Тоді ми отримаємо поєднання з n елементів по m.
Їх загальна кількість позначається і може бути обчислено за формулою:
З цієї формули ясно, що
Зауважимо, що можна скласти тільки одне поєднання з n елементів по n. яке містить всі n елементів. Формула числа поєднань дає це значення, якщо тільки прийняти, що 0! = 1. що є визначенням 0.
Відповідно до цього визначення отримаємо:
Загальна кількість поєднань можна обчислити, користуючись і іншим виразом:
П р и м і р. Знайти число поєднань з п'яти елементів: a, b, c, d, e по три.
Ці поєднання: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.
29) За якою формулою обчислюється число перестановок з n елементів, якщо елементи повторюються?
Перестановками з n елементів називаються розміщення з цих n елементів по n (Перестановки - окремий випадок розміщень).
Число перестановок без повторень (n різних елементів) обчислюється за формулою:
Число перестановок c повтореннями (k різних елементів, де елементи можуть повторюватися m1. M2. ..., mk раз і m1 + m2 + ... + mk = n, де n - загальна кількість елементів) обчислюється за формулою:
Приклад. Візьмемо літери Б, А, Р. Які перестановки з цих букв можна отримати? Скільки таких наборів вийде, якщо: 1) літери в наборі не повторюються; 2) буква А повторюється два рази?
1. Вийдуть набори: БАР, БРА, АРБ, АБР, РАБ, РБА.
За формулою (3.3) отримуємо: наборів.
2. Вийдуть набори: БАРУ, БРАА, Баарь, ААРБ, ААБР, Абар, араби, гарба, АБРА, РАБА, Раабе, РБАА.
За формулою (3.4) отримуємо: наборів.
Приклад. Скільки шестизначних чисел можна скласти з цифр 0, 1, 2, 3, 4, 5 так, щоб цифри в числі не повторювалися?
Рішення. З даних шести цифр можна скласти Р6 = 6! = 720 перестановок. Але числа, що починаються на нуль, не є шестизначними. Такі числа відрізняються один від одного перестановкою п'яти інших цифр, значить, їх буде Р5 = 120. Тому шестизначних чисел буде 720 - 120 = 600 чисел.
Приклад. Скількома способами можна розставити білі фігури (2 тури, 2 коня, 2 слона, ферзь і король) на першій лінії шахівниці?
Рішення. Перша лінія шахівниці є 8 клітин, на яких і треба розташувати ці 8 фігур. Різні варіанти розташування будуть відрізнятися тільки порядком фігур, значить, це будуть перестановки з повтореннями Р8 (2,2,2).
За формулою (3.4) отримуємо: способів.
30) Якою формулою визначається число розміщень з повтореннями з n елементів по m елементів?
Розміщеннями з n елементів по m елементів (m Число розміщень без повторень з n по m (n різних елементів) обчислюється за формулою: Розміщеннями з повтореннями з n елементів по m називаються упорядоченниеm -елементние вибірки, в яких елементи можуть повторюватися. Число розміщень з повтореннями обчислюється за формулою: Приклад. Візьмемо літери Б, А, Р. Які розміщення з цих букв, взятих по дві, можна отримати? Скільки таких наборів вийти, якщо: 1) літери в наборі не повторюються; 2) літери можуть повторюватися? 1. Вийдуть такі набори: БА, БР, АР, АБ, РБ, РА. За формулою (3.1) отримуємо: наборів. 2. Вийдуть набори: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА. За формулою (3.2) отримуємо: наборів. Приклад. Уздовж дороги стоять 6 світлофорів. Скільки може бути різних комбінацій їх сигналів, якщо кожен світлофор має 3 стани: "червоний", "жовтий", "зелений"? Рішення. Випишемо кілька комбінацій: КККЖЗЗ, ЗЗЗЗЗЗ, КЖЗКЖЗ. Ми бачимо, що склад вибірки змінюється і порядок елементів істотний (адже якщо, наприклад, у вибірці КЖЗКЖЗ поміняти місцями К і Ж, ситуація на дорозі буде інший). Тому застосовуємо формулу (3.2) і обчислюємо число розміщень з повтореннями з 3 по 6, отримуємо комбінацій. 31) Якою формулою визначається число поєднань з повтореннями з n елементів по m елементів? Поєднаннями з n елементів по m елементів називаються комбінації, складені з даних n елементів по m елементів, які відрізняються хоча б одним елементом (відміну поєднань від розміщень в тому, що в поєднаннях не враховується порядок елементів). Число сполучень без повторень (n різних елементів, взятих по m) обчислюється за формулою: Число сполучень c повтореннями (n елементів, взятих по m. Де елементи в наборі можуть повторюватися) обчислюється за формулою: Приклад. Візьмемо літери Б, А, Р. Які поєднання з цих букв, взятих по дві, можна отримати? Скільки таких наборів вийде, якщо: 1) літери в наборі не повторюються; 2) можна брати по два однакові літери. За формулою (3.5) отримуємо: наборів. 2. Вийдуть набори: ББ, БА, БР, АА, АР, РР. За формулою (3.6) отримуємо: наборів. Приклад. З 20 учнів треба вибрати двох чергових. Скількома способами це можна зробити? Рішення. Треба вибрати двох чоловік з 20. Ясно, що від порядку вибору нічого не залежить, тобто Іванов-Петров або Петров-Іванов - це одна і та ж пара чергових. Отже, це будуть поєднання з 20 по 2. За формулою (3.5) отримуємо: способів. Приклад. У хлібному відділі є булки білого і чорного хліба. Скількома способами можна купити 6 булок хліба? Рішення. Позначаючи булки білого і чорного хліба буквами Б і Ч, складемо кілька вибірок: ББББББ, ББЧЧББ, ЧЧЧЧЧБ. Склад змінюється від вибірки до вибірки, порядок елементів є несуттєвим, значить це - поєднання з повтореннями з 2 по 6. За формулою (3.6) отримуємо способів. Зробити перевірку і випишемо всі варіанти покупки: ББББББ, БББББЧ, ББББЧЧ, БББЧЧЧ, ББЧЧЧЧ, БЧЧЧЧЧ, ЧЧЧЧЧЧ. Їх дійсно 7. 32) Що називають сумою двох подій? Сумою двох подій і називають подію, що складається в появі події. або події. або обох цих подій. 33) Що називають твором двох подій? Твором двох подій і називають подію. яке у спільному появу цих подій. 34) Чому дорівнює ймовірність суми двох несумісних подій? Подія називають незалежним від події. якщо поява події не змінює ймовірності появи події. тобто якщо умовна ймовірність події дорівнює його безумовній ймовірності: 35) Сформулюйте теорему додавання? Імовірність р (А + В) суми подій А і В дорівнює Доведемо теорему додавання для схеми випадків. Нехай п - число можливих результатів досвіду, тА - число випадків, сприятливих події А. телевізорами - число випадків, сприятливих події В. а Тав - число фіналів досвіду, при яких відбуваються обидві події (тобто результатів, сприятливих твору АВ). Тоді число випадків, при яких має місце подія А + В. одно тА + телевізорами - Тав (так як в сумі (тА + телевізорами) ТАВ враховано двічі: як результати, сприятливі А. та наслідки, сприятливі В). Отже, ймовірність суми можна визначити за формулою 2,2 що й треба було довести. 36) Чому дорівнює сума ймовірностей подій, що утворюють повну групу? Сума ймовірностей попарно несумісних подій. утворюють повну групу, дорівнює одиниці: 37) Сформулюйте теорему множення ймовірностей залежних подій? Імовірність добутку двох подій (спільного появи цих подій) дорівнює добутку ймовірності однієї з них на умовну ймовірність іншого, обчислену за умови, що перша подія вже наступило. 38) Що означає, що дві події незалежні? Кілька подій називають незалежними в сукупності. якщо незалежні кожні два з них і незалежні кожне подія і всі можливі твори інших. 39) Чому дорівнює ймовірність добутку двох незалежних подій? Можливість спільного появи кількох подій, незалежних в сукупності, дорівнює добутку ймовірностей цих подій: 40) Сформулюйте теорему додавання ймовірностей сумісних подій? Дві події називаються спільними. якщо поява одного з них не виключає появи іншого в одному і тому ж досвіді. Приклад. Надходження в магазин одного виду товару - подія. Надходження другого виду товару - подія. Вступити ці товари можуть і одночасно. Тому і - спільні події. Теорема. Імовірність появи хоча б одного з двох спільних подій дорівнює сумі ймовірностей цих подій без ймовірності їх спільного появи Доведення. Подія настане, якщо настане одна з трьох несумісних подій. . . По теоремі додавання ймовірностей несумісних подій маємо Подія відбудеться, якщо настане одна з двох несумісних подій:. . Знову застосовуючи теорему додавання ймовірностей несумісних подій, отримуємо. Звідки Аналогічно для події Звідки Підставивши (2.7) і (2.8) в (2.6), знаходимо Приклад. Якщо ймовірність надходження в магазин одного виду товару дорівнює P (A) = 0,4, а другого товару - P (B) = 0,5, і якщо допустити, що ці події незалежні, але сумісні, то ймовірність суми подій дорівнює P (A + B) = 0,4 + 0,5 - 0,4 × 0,5 = 0,7.
Сумою декількох подій називають подію, що складається в появі хоча б одного з цих подій.
.
Властивість незалежності подій взаємно: якщо подія не залежить від події. то і подія не залежить від події.
Теорема. Можливість спільного появи двох незалежних подій дорівнює добутку ймовірності цих подій:
.
Кілька подій називають попарно незалежними. якщо кожні два з них незалежні.
Кілька подій називають незалежними в сукупності. якщо незалежні кожні два з них і незалежні кожне подія і всі можливі твори інших.
.
Протилежними називають два єдино можливих події, що утворюють повну групу.
Подія, протилежне події. прийнято позначати.
.