Комбінаторика: основні правила і формули. Формули комбінаторики Перестановки і теорія ймовірностей
Комбінаторика - це розділ математики, в якому вивчаються питання про те, скільки різних комбінацій, підлеглих тим чи іншим умовам, можна скласти з заданих об'єктів. Основи комбінаторики дуже важливі для оцінки ймовірностей випадкових подій, тому що саме вони дозволяють підрахувати принципово можливу кількість різних варіантів розвитку подій.
Основна формула комбінаторики
Нехай є k груп елементів, причому i-я група складається з n i елементів. Виберемо по одному елементу з кожної групи. Тоді загальне число N способів, якими можна зробити такий вибір, визначається співвідношенням N \u003d n 1 * n 2 * n 3 * ... * n k.
Приклад 1. Пояснимо це правило на простому прикладі. Нехай є дві групи елементів, причому перша група складається з n 1 елементів, а друга - з n 2 елементів. Скільки різних пар елементів можна скласти з цих двох груп, таким чином, щоб в парі було по одному елементу від кожної групи? Припустимо, ми взяли перший елемент з першої групи і, не змінюючи його, перебрали всі можливі пари, змінюючи тільки елементи з другої групи. Таких пар для цього елемента можна скласти n 2. Потім ми беремо другий елемент з першої групи і також складаємо для нього всі можливі пари. Таких пар теж буде n 2. Так як в першій групі всього n 1 елемент, всього можливих варіантів буде n 1 * n 2.
Приклад 2. Скільки тризначних парних чисел можна скласти з цифр 0, 1, 2, 3, 4, 5, 6, якщо цифри можуть повторюватися?
Рішення:n 1 \u003d 6 (тому що в якості першої цифри можна взяти будь-яку цифру з 1, 2, 3, 4, 5, 6), n 2 \u003d 7 (тому що в якості другої цифри можна взяти будь-яку цифру з 0 , 1, 2, 3, 4, 5, 6), n 3 \u003d 4 (тому що в якості третьої цифри можна взяти будь-яку цифру з 0, 2, 4, 6).
Отже, N \u003d n 1 * n 2 * n 3 \u003d 6 * 7 * 4 \u003d 168.
У тому випадку, коли всі групи складаються з однакового числа елементів, тобто n 1 \u003d n 2 \u003d ... n k \u003d n можна вважати, що кожен вибір проводиться з однією і тією ж групи, причому елемент після вибору знову повертається в групу. Тоді число всіх способів вибору одно n k. Такий спосіб вибору в комбінаторики носить назву вибірки з поверненням.
Приклад 3. Скільки всіх чотиризначних чисел можна скласти з цифр 1, 5, 6, 7, 8?
Рішення. Для кожного розряду чотиризначного числа є п'ять можливостей, значить N \u003d 5 * 5 * 5 * 5 \u003d 5 4 \u003d 625.
Розглянемо безліч, що складаються з n елементів. Це безліч в комбінаториці називається генеральною сукупністю.
Число розміщень з n елементів по m
Визначення 1. розміщенням з n елементів по m в комбінаториці називається будь-який упорядкований набір з m різних елементів, вибраних з генеральної сукупності в n елементів.
Приклад 4.Різними розміщеннями з трьох елементів (1, 2, 3) по два будуть набори (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2 ). Розміщення можуть відрізнятися один від одного як елементами, так і їх порядком.
Число розміщень в комбінаториці позначається A n m і обчислюється за формулою:
зауваження: n! \u003d 1 * 2 * 3 * ... * n (читається: "ен факторіал"), крім того вважають, що 0! \u003d 1.
приклад 5. Скільки існує двозначних чисел, в яких цифра десятків і цифра одиниць різні і непарні?
Рішення: тому непарних цифр п'ять, а саме 1, 3, 5, 7, 9, то це завдання зводиться до вибору і розміщення на дві різні позиції двох з п'яти різних цифр, тобто зазначених чисел буде:
Визначення 2. Поєднанням з n елементів по m в комбінаториці називається будь-який невпорядкований набір з m різних елементів, вибраних з генеральної сукупності в n елементів.
приклад 6. Для безлічі (1, 2, 3) поєднаннями є (1, 2), (1, 3), (2, 3).
Число сполучень з n елементів по m
Число сполучень позначається C n m і обчислюється за формулою:
Приклад 7.Скількома способами читач може вибрати дві книжки з шести наявних?
Рішення:Число способів дорівнює числу сполучень з шести книжок по дві, тобто одно:
Перестановки з n елементів
Визначення 3. Перестановкою з n елементів називається будь-який упорядкований набір цих елементів.
Приклад 7a. Всілякими перестановками безлічі, що складається з трьох елементів (1, 2, 3) є: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), ( 3, 2, 1), (3, 1, 2).
Число різних перестановок з n елементів позначається P n і обчислюється за формулою P n \u003d n !.
Приклад 8. Скількома способами сім книг різних авторів можна розставити на полиці в один ряд?
Рішення:ця задача про кількість перестановок семи різних книг. Є P 7 \u003d 7! \u003d 1 * 2 * 3 * 4 * 5 * 6 * 7 \u003d 5040 способів здійснити розстановку книг.
Обговорення.Ми бачимо, що число можливих комбінацій можна порахувати за різними правилами (перестановки, поєднання, розміщення) причому результат вийде різний, тому що принцип підрахунку і самі формули відрізняються. Уважно подивившись на визначення, можна помітити, що результат залежить від кількох факторів одночасно.
По-перше, від того, з якої кількості елементів ми можемо комбінувати їх набори (наскільки велика генеральна сукупність елементів).
По-друге, результат залежить від того, якої величини набори елементів нам потрібні.
І останнє, важливо знати, чи є для нас істотним порядок елементів в наборі. Пояснимо останній фактор на наступному прикладі.
Приклад 9.На батьківських зборах присутній 20 осіб. Скільки існує різних варіантів складу батьківського комітету, якщо в нього повинні увійти 5 осіб?
Рішення:У цьому прикладі нас не цікавить порядок прізвищ у списку комітету. Якщо в результаті в його складі виявляться одні і ті ж люди, то за змістом для нас це один і той же варіант. Тому ми можемо скористатися формулою для підрахунку числа сполученьз 20 елементів по 5.
Інакше йтимуть справи, якщо кожен член комітету спочатку відповідає за певний напрям роботи. Тоді при одному і тому ж обліковому складі комітету, всередині нього можливо 5! варіантів перестановок, Які мають значення. Кількість різних (і за складом, і за сферою відповідальності) варіантів визначається в цьому випадку числом розміщень з 20 елементів по 5.
Завдання для самоперевірки
1. Скільки тризначних парних чисел можна скласти з цифр 0, 1, 2, 3, 4, 5, 6, якщо цифри можуть повторюватися?
Оскільки число парне на третьому місці може стояти 0, 2, 4, 6, тобто чотири цифри. На другому місці може стояти будь-яка з семи цифр. На першому місці може стояти будь-яка з семи цифр крім нуля, тобто 6 можливостей. Результат \u003d 4 * 7 * 6 \u003d 168.
2. Скільки існує п'ятизначних чисел, які однаково читаються зліва направо і справа наліво?
На першому місці може стояти будь-яка цифра крім 0, тобто 9 можливостей. На другому місці може стояти будь-яка цифра, тобто 10 можливостей. На третьому місці теж може стояти будь-яка цифра з, тобто 10 можливостей. Четверта і п'ята цифри визначені заздалегідь, вони збігаються з першої і другої, отже, число таких чисел 9 * 10 * 10 \u003d 900.
3. У класі десять предметів і п'ять уроків в день. Скількома способами можна скласти розклад на один день?
4. Скількома способами можна вибрати 4 делегата на конференцію, якщо в групі 20 чоловік?
n \u003d C 20 4 \u003d (20!) / (4! * (20-4)!) \u003d (16! * 17 * 18 * 19 * 20) / ((1 * 2 * 3 * 4) * (16! )) \u003d (17 * 18 * 19 * 20) / (1 * 2 * 3 * 4) \u003d 4845.
5. Скількома способами можна розкласти вісім різних листів по восьми різних конвертах, якщо в кожен конверт кладеться тільки один лист?
У перший конверт можна покласти 1 з восьми листів, у другій одне з семи залишилися, в третій одне з шість т.д. n \u003d 8! \u003d 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 \u003d 40320.
6. З трьох математиків і десяти економістів треба створити комісію, що складається з двох математиків і шести економістів. Скількома способами це можна зробити?
Все N елементів, і жоден з них не повторюється, то це завдання про кількість перестановок. Рішення можна знайти простим. На першому місці в ряду може стояти будь-який з N елементів, отже, виходить N варіантів. На другому місці - будь-який, крім того, який вже був використаний для першого місця. Отже, для кожного з N вже знайдених варіантів є (N - 1) варіантів другого місця, і загальна кількість комбінацій стає N * (N - 1).
Це ж можна повторити для інших елементів ряду. Для самого останнього місця залишається тільки один варіант - останній залишився елемент. Для передостаннього - два варіанти, і так далі.
Отже, для ряду з N неповторюваних елементів можливих перестановок дорівнює добутку всіх цілих від 1 до N. Цей твір називається факторіалом числа N і позначається N! (Читається «Ен факторіал»).
У попередньому випадку кількість можливих елементів і кількість місць ряду збігалися, і їх число дорівнювало N. Але можлива ситуація, коли в ряду менше місць, ніж є можливих елементів. Іншими словами, кількість елементів у вибірці дорівнює деякому числу M, причому M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
По-перше, може знадобитися порахувати загальну кількість можливих способів, якими можна вибудувати в ряд M елементів з N. Такі способи називаються розміщеннями.
По-друге, дослідника може цікавити число способів, якими можна вибрати M елементів з N. При цьому порядок розташування елементів вже не важливий, але будь-які два варіанти повинні відрізнятися між собою хоча б одним елементом. Такі способи називаються сполученнями.
Щоб знайти кількість розміщень по M елементів з N, можна вдатися до такого ж способу міркувань, як і в випадку з перестановками. На першому місці тут як і раніше може стояти N елементів, на другому (N - 1), і так далі. Але для останнього місця кількість можливих варіантів дорівнює не одиниці, а (N - M + 1), оскільки, коли розміщення буде закінчено, залишиться ще (N - M) невикористаних елементів.
Таким чином, число розміщень по M елементів з N дорівнює добутку всіх цілих чисел від (N - M + 1) до N, або, що те ж саме, приватному N! / (N - M) !.
Очевидно, що кількість сполучень по M елементів з N буде менше кількості розміщень. Для кожного можливого поєднання є M! можливих розміщень, що залежать від порядку елементів цього поєднання. Отже, щоб знайти це кількість, потрібно розділити число розміщень по M елементів з N на N !. Іншими словами, кількість сполучень по M елементів з N одно N! / (M! * (N - M)!).
Перш за все, розберемо основні поняття комбінаторики - вибірки і їх типи: перестановки, розміщення і поєднання. Знати їх необхідно для вирішення великої частини ЄДІ 2020 по математиці обох рівнів, а також дев'ятикласникам для здачі ОГЕ. Почнемо з прикладу.
Перестановки. Підрахунок числа перестановок.
Уявіть собі, що ви обрали професію, яка, здавалося б, ні яким чином не пов'язана з математикою, наприклад, дизайнер інтер'єрів. Уявіть собі, що замовник висловив вам прохання:
"Розставте 4 книги на полиці так, щоб бордовий і синій томи не стояли поруч. Покажіть мені усе варіанти розстановки. Я виберу найкращий. "
Що ви станете робити? Найімовірніше, почнете розставляти і показувати. Однак, щоб не заплутатися, не пропустити жодного з можливих варіантів і не повторюватися, потрібно робити це з якої-небудь системі.
Наприклад, спочатку залишаємо на першому місці бордовий тому, поруч з ним може перебувати зелений або оранжевий. Якщо на другому місці стоїть зелений тому, то далі можуть стояти або помаранчевий і синій, або синій і помаранчевий. Якщо на другому місці стоїть помаранчевий тому, то далі можуть стояти або зелений і синій, або синій і зелений. Разом, виходить 4 можливих варіанти.
На першому місці може стояти будь-який з 4-ох томів, значить описану процедуру треба повторити ще 3 рази. Випадок, коли на першому місці стоїть синій тому, виходить такими ж міркуваннями. 
А такі два випадки відрізняються тим, що на трьох місцях повинні знаходитися бордовий і синій томи, але не поруч. Наприклад, коли на першому місці стоїть зелений тому, помаранчевий тому повинен стояти на третьому місці, щоб розділяти бордовий і синій томи, які можуть займати, відповідно, або друге і четверте місця, або четверте і друге.
В результаті у нас вийшло всього 12 варіантів розстановки 4-ох книг на полиці з заданим обмеженням. Багато це чи мало? Якщо витратити по одній хвилині на переміщення книг і обговорення отриманого варіанту з замовником, то, мабуть, нормально. 12 хвилин можна і книжки посувати, і поговорити. (Спробуйте порахувати, скільки вийшло б перестановок 4-ох книг без всяких обмежень?)
А тепер уявіть собі, що у замовника книг більше, ніж 4. Ну хоча б 5. Зрозуміло, що і варіантів розстановки буде більше, і реально переставляти їх з місця на місце довше, і заплутатися і почати повторюватися легше ... Значить кидатися в бій без підготовки вже не варто. Потрібно спочатку запланувати варіанти на папері. Для стислості Занумеруем наші кольорові томи і будемо переставляти на папері їх номери. Щоб менше помилятися, спочатку випишемо всі варіанти перестановки, а потім викреслимо ті з них, які підпадають під обмеження. Отже:
"Розставте 5 книг на полиці так, щоб 1-й і 2-й томи не стояли поруч. Покажіть усе варіанти перестановок. "
У нас 5 книг (або 5 цифр), кожна з яких може стояти на першому місці. Зробимо для кожного з цих 5-ти випадків свою табличку. На другому місці може стояти будь-яка з решти 4-ох цифр, для кожної з них зарезервуємо стовпчик в табличці.
У кожному стовпчику поміщаємо пари рядків, в яких на третьому місці стоїть одна з решти 3-ох цифр, а дві останні цифри міняються місцями. Таким чином ми акуратно виписуємо усе варіанти перестановок. Підрахуємо їх загальне число.
5 (Таблиць) × 4(Стовпчика) × 3(Пари рядків) × 2(Рядки) × 1 (варіант) \u003d 120 (Варіантів).
І, нарешті, викреслимо з усіх таблиць варіанти, що містять "12" або "21". Таких виявилося по 6 в першій і другій табличках і по 12 в останніх 3-ох, всього 48 варіантів, які задовольняють обмеження. Значить замовнику треба показати 120 - 48 \u003d 72 варіанта розташування 5-ти книг. На це піде більше години, навіть якщо витрачати на обговорення кожного варіанта тільки хвилину.
Тільки де ви бачили одного чоловіка, який для перестановки п'яти книг стане наймати дизайнера? Реально такі завдання виникають в бібліотеках, де потрібно розставити книги для зручності відвідувачів, у великих книжкових магазинах, де потрібно розставити книги так, щоб забезпечити збільшення попиту, і т.п. Тобто там, де книг не одиниці, і навіть не десятки, а сотні і тисячі.
Вважати варіанти перестановок доводиться не тільки для книг. Це може знадобитися для великого числа будь-яких об'єктів практично в будь-якій сфері діяльності. Значить, як дизайнерам, так і людям інших професій може знадобитися помічник, а ще краще інструмент для полегшення підготовчого етапу, аналізу можливих результатів і скорочення обсягу непродуктивного праці. Такі інструменти створювали і створюють вчені-математики, а потім віддають їх суспільству у вигляді готових формул. Математики не обійшли своєю увагою питання, пов'язані з перестановками, а також з розміщеннями і поєднаннями різних елементів. Відповідними формулами вже не одне століття. Ці формули дуже прості, підростаючої частини суспільства їх "вручають" на уроках шкільної математики. Тому все, що було написано вище, це по-суті, "винахід велосипеда", до якого довелося вдатися через припущення, що дизайнерові інтер'єрів ніколи не знадобиться математика. Що ж, відмовимося від цього припущення. Повторимо математичні поняття, а потім знову повернемося до задачі про книжковій полиці.
комбінаторикою називається область математики, в якій вивчаються питання про те, скільки різних комбінацій, підлеглих тим чи іншим умовам, можна скласти з елементів заданої множини. Складаючи комбінації, ми фактично вибираємо з цього безлічі різних об'єктів та об'єднуємо їх в групи по нашим потребам, тому замість слова "комбінації", часто використовують слово "вибірки" елементів.Формула для числа перестановок.
перестановками називаються такі вибірки елементів, які відрізняються тільки порядком розташування елементів, але не самими елементами.
Якщо перестановки виробляються на безлічі з n елементів, їх число
визначається за формулою
P n
= n·( n-1) · ( n-2) ... 3 · 2 · 1 \u003d n!
n! - позначення, яке використовують для короткої записи твори всіх натуральних чисел від 1 до n включно і називають " n-факторіал "(в перекладі з англійської" factor "-" множник ").
Таким чином, загальне число перестановок 5-ти книг P 5 \u003d 5! \u003d 1 · 2 · 3 · 4 · 5 \u003d 120, що ми і отримали вище. Фактично ми виводили цю формулу для маленького прикладу. Тепер вирішимо приклад побільше.
завдання 1.
На книжковій полиці поміщається 30 томів. Скількома способами їх можна розставити, щоб при цьому 1-й і 2-й томи не стояли поруч?
Рішення.
Визначимо загальне число перестановок з 30 елементів по формулі P 30=30!
Щоб обчислити число "зайвих" перестановок, спочатку визначимо, скільки варіантів, в яких 2-й том знаходиться поруч з 1-им праворуч від нього. У таких перестановках 1-ий том може займати місця з першого по 29-е, а 2-й з другого по 30-е - всього 29 місць для цієї пари книг. І при кожному такому положенні перших двох томів інші 28 книг можуть займати інші 28 місць в довільному порядку. Варіантів перестановки 28 книг P 28\u003d 28! Всього "зайвих" варіантів при розташуванні 2-го тому праворуч від 1-го вийде 29 · 28! \u003d 29 !.
Аналогічно розглянемо випадок, коли 2-й том розташований поруч з 1-им, але зліва від нього. Виходить таке ж число варіантів 29 · 28! \u003d 29 !.
Значить все "зайвих" перестановок 2 · 29 !, а потрібних способів розстановки 30! -2 · 29! Обчислимо це значення.
30! \u003d 29! · 30; 30! -2 · 29! \u003d 29! · (30-2) \u003d 29! · 28.
Отже, нам потрібно перемножити всі натуральні числа від 1 до 29 і ще раз помножити на 28.
відповідь: 2,4757335 · 10 32.
Це дуже велике число (після двійки ще 32 цифри). Навіть якщо затратити секунду на кожну перестановку, то будуть потрібні мільярди років. Чи варто виконувати таку вимогу замовника, або краще вміти обґрунтовано заперечити йому і настояти на застосуванні додаткових обмежень?
Перестановки і теорія ймовірностей.
Ще частіше необхідність підрахунку числа варіантів виникає в теорії ймовірностей. Продовжимо книжкову тему наступним завданням.
завдання 2.
На книжковій полиці стояло 30 томів. Дитина впустив книги з полиці, а потім розставив їх у випадковому порядку. Яка ймовірність того, що він нЕ поставив 1-й і 2-й томи поруч?
Рішення.
Спочатку визначимо ймовірність події А, що складається в тому, що дитина поставив 1-й і 2-й томи поруч.
Елементарне подія - якась розстановка книг на полиці. Зрозуміло, що загальне число всіх елементарних подій буде дорівнює загальній кількості всіх можливих перестановок P 30=30!.
Число елементарних подій, що сприяють події А, дорівнює числу перестановок, в яких 1-й і 2-й томи стоять поруч. Ми розглядали такі перестановки, вирішуючи попередню задачу, і отримали 2 · 29! перестановок.
Імовірність визначаємо діленням числа сприятливих елементарних подій на число всіх можливих елементарних подій:
P (A) \u003d 2 · 29! / 30! \u003d 2 · 29! / (29! · 30) \u003d 2/30 \u003d 1/15.
Подія В - дитина нЕ поставив 1-й і 2-й томи поруч - протилежно події A, значить його ймовірність P (B) \u003d 1 - P (A) \u003d 1-1 / 15 \u003d 14/15 \u003d 0,9333
відповідь:0,9333.
Замечаніe: Якщо незрозуміло, як скорочуються дроби з факторіалами, то згадайте, що факторіал це короткий запис твору. Її завжди можна розписати довго і закреслити повторювані множники в чисельнику і в знаменнику.
У відповіді вийшло число близьке до одиниці, це означає, що при такій кількості книг випадково поставити два заданих томи поруч складніше, чому не поставити.
Розміщення. Підрахунок числа розміщень.
Тепер припустимо, що у замовника багато книг і неможливо розмістити їх все на відкритих полицях. Його прохання полягає в тому, що потрібно вибрати певну кількість будь-яких книг і розмістити їх красиво. Красиво вийшло або некрасиво це питання смаку замовника, тобто він знову хоче подивитися усе варіанти і прийняти рішення сам. Наше завдання полягає в тому, щоб порахувати кількість всіх можливих варіантів розміщення книг, обгрунтовано переконати його і ввести розумні обмеження.
Щоб розібратися в ситуації, давайте спочатку вважати, що "багато" - це 5 книг, що у нас всього одна полиця, і що на ній вміщається лише 3 томи. Що ми будемо робити?
Вибираємо одну з 5-ти книг і ставимо на перше місце на полиці. Це ми можемо зробити 5-ю способами. Тепер на полиці залишилося два місця і у нас залишилося 4 книги. Другу книгу ми можемо вибрати 4-ма способами і поставити поряд з однією з 5-ти можливих перших. Таких пар може бути 5 · 4. Залишилося 3 книги і одне місце. Одну книгу з 3-ох можна вибрати 3-ма способами і поставити поряд з однією з можливих 5 · 4 пар. Вийде 5 · 4 · 3 різноманітних трійок. Значить все способів розмістити 3 книги з 5-ти 5 · 4 · 3 \u003d 60.
На малюнку представлені тільки 4 варіанти розміщення з 60 можливих. Порівняйте картинки. Зверніть увагу, що розміщення можуть відрізнятися один від одного або тільки порядком проходження елементів, як перші дві групи, або складом елементів, як такі.
Формула для числа розміщень.
розміщеннями з n елементів по m (Місць) називаються такі вибірки, які маючи по m елементів, вибраних з числа даних n елементів, відрізняються одна від одної або складом елементів, або порядком їх розташування.
Число розміщень з n по m
позначається A n m і визначається за формулою
A n m \u003d n·( n - 1) · ( n - 2) · ... · ( n − m + 1) = n!/(N - m)!
Спробуємо обчислити по цій формулі A n n, Тобто число розміщень з n по n.
A n n = n·( n-1) · ( n-2) · ... · ( n-n + 1) =
n·( n-1) · ( n-2) · ... · 1 \u003d n!
Таким чином, A n n = P n = n!
Нічого дивного в тому, що число розміщень з n по n дорівнювала числу перестановок n елементів, адже ми використовували для складання розміщень все безліч елементів, а значить вони вже не можуть відрізнятися один від одного складом елементів, тільки порядком їх розташування, а це і є перестановки.
завдання 3.
Скількома способами можна розставити 15 томів на книжковій полиці, якщо вибирати їх з наявних 30-ти книг?
Рішення.
Визначимо загальне число розміщень з 30 елементів по 15 по формулі
A 30 15 \u003d 30 · 29 · 28 · ... · (30-15 + 1) \u003d 30 · 29 · 28 · ... · 16 \u003d 202843204931727360000.
відповідь: 202843204931727360000.
Будете розміщувати реальні книги? Успіхів! Порахуйте, скільки життів буде потрібно, щоб перебрати всі варіанти.
завдання 4.
Скількома способами можна розставити 30 книг на двох полицях, якщо на кожній з них міститься тільки по 15 томів?
Рішення.
Спосіб I.Уявімо собі, що першу полку ми заповнюємо так само, як в попередньому завданні. Тоді варіантів розміщення з 30-ти книг по 15 буде A 30 15 \u003d 30 · 29 · 28 · ... · (30-15 + 1) \u003d 30 · 29 · 28 · ... · 16.
І при кожному розміщенні книг на першій полиці ми ще P 15 \u003d 15! способами можемо розставити книги на другій полиці. Адже для другої полиці у нас залишилося 15 книг на 15 місць, тобто можливі тільки перестановки.
Всього способів буде A 30 15 · P 15, При цьому твір всіх чисел від 30 до 16 ще потрібно буде помножити на добуток всіх чисел від 1 до 15, вийде твір всіх натуральних чисел від 1 до 30, тобто 30!
Спосіб II.
Тепер уявімо собі, що у нас була одна довга полку на 30 місць. Ми розставили на ній все 30 книг, а потім розпиляли полку на дві рівні частини, щоб задовольнити умові завдання. Скільки варіантів розстановки могло бути? Стільки, скільки можна зробити перестановок з 30 книг, тобто P 30 = 30!
відповідь: 30!.
Не важливо, як ви вирішуєте задачку. Ви її вирішуєте так, як уявляєте собі свої дії в життєвій ситуації. Важливо не відступати від логіки в своїх міркуваннях, щоб в будь-якому випадку отримати правильну відповідь.
Розміщення і теорія ймовірностей.
У теорії ймовірностей завдання на розміщення зустрічаються не так часто, ніж завдання на інші типи вибірок, оскільки розміщення мають більше розпізнавальних ознак - і порядок, і склад елементів, а значить менше схильні до випадковим вибором.
завдання 5.
На книжковій полиці знаходиться зібрання творів одного автора в 6 томах. Книги однакового формату розташовані в довільному порядку. Читач, не дивлячись, бере 3 книги. Яка ймовірність того, що він взяв перші три томи?
Рішення.
Подія A - у читача перші три томи. З урахуванням порядку вибору він міг взяти їх 6-ю способами. (Це перестановки з 3-ох елементів P 3
\u003d 3! \u003d 1 · 2 · 3 \u003d 6, які легко перерахувати 123, 132, 213, 231, 312, 321.)
Таким чином, число сприятливих елементарних подій дорівнює 6.
Загальна кількість можливих елементарних подій дорівнює числу розміщень з 6-ти по 3, тобто A 6 3 \u003d 6 · ... · (6-3 + 1) \u003d 6 · 5 · 4 \u003d 120.
P (A) \u003d 6/120 \u003d 1/20 \u003d 0,05.
відповідь: 0,05.
Сполучення. Підрахунок числа сполучень.
І останній випадок - все книги замовника одного кольору і одного розміру, але на полиці поміщається лише частина з них. Здавалося б проблем у дизайнера немає зовсім, вибирай стільки книг із загального числа, скільки потрібно, і розставляй їх на полиці в довільному порядку, адже книги зовні невиразні. Але вони відрізняються, і істотно! Ці книги різні за змістом. І замовнику, можливо, не все одно, де знаходяться трагедії Шекспіра, а де детективи Рекса Стаута, на відкритій полиці або в шафі. Таким чином, у нас виникає ситуація, коли важливий склад елементів вибірки, але є несуттєвим порядок їх розташування.
На малюнку показані дві вибірки з "зібрання творів одного автора в 5 томах". Перша більше сподобається замовнику, якщо він частіше перечитує ранні твори цього автора, поміщені в перших трьох томах, друга - якщо частіше звертається до пізньої творчості, поміщеним в останніх томах. Виглядають обидві групи однаково красиво (або однаково негарно) і неважливо, чи буде група розташована як 123 або як 321 ...
Формула для числа сполучень.
Невпорядковані вибірки називаються з n елементів по m і позначаються З n m.
число сполучень
визначається за формулою З n m \u003d n!/(n - m)! / m!
У цій формулі присутні два подільника і в якості знака ділення використаний символ " /
", Який більш зручний для веб-сторінки. Але розподіл можна також позначати двокрапкою" :
"Або горизонтальною лінією" --- ". В останньому випадку формула виглядає як звичайна дріб, в якій послідовне поділ поданий двома співмножники в знаменнику 
. Для тих, кому зрозуміліше представлення у вигляді дробу, все формули продубльовані на початку і в самому кінці сторінки. Розбираючи вирішення завдань порівнюйте мою запис зі звичною для себе.
Крім того, всі множники і подільники в цій формулі є твори послідовних натуральних чисел, тому дріб добре скорочується, якщо її розписати докладно. Але докладний скорочення я в задачах пропускаю, його легко перевірити самостійно.
Зрозуміло, що для однакових вихідних множин з n елементів і однакових обсягів вибірок (по m елементів) число поєднань має бути менше, ніж число розміщень. Адже при підрахунку розміщень для кожної обраної групи ми ще враховуємо всі перестановки обраних m елементів, а при підрахунку поєднань перестановки не враховуємо: З n m = A n m/P m = n!/(n-m)!/m!
завдання 6.
Скількома способами можна розставити 15 томів на книжковій полиці, якщо вибирати їх з наявних зовні нерозпізнаних 30-ти книг?
Рішення.
Ми вирішуємо цю задачу в контексті роботи дизайнера інтер'єрів, тому порядок проходження на полиці 15-ти обраних зовні однакових книг не має значення. Потрібно визначити загальне число сполучень з 30 елементів по 15 по формулі
З 30 15 = 30!
/(30
− 15)!/15!
= 155117520.
відповідь: 155117520.
завдання 7.
Скількома способами можна розставити 30 зовні нерозпізнаних книг на двох полицях, якщо на кожній з них міститься тільки по 15 томів?
Якщо ми знову відповідаємо на це питання з точки зору дизайнера інтер'єрів, то порядок проходження книг на кожній з полиць є несуттєвим. Але замовнику може бути важливо чи неважливо, як книги розподілені між полицями.
1) Наприклад, якщо обидві полиці знаходяться поруч, обидві відкриті, обидві на однаковій висоті, то замовник може сказати, що це не має значення. Тоді відповідь очевидна - 1 спосіб, так як при розстановці використовується ввесь люд з 30-ти книг, і ніякі перестановки не враховуються.
2) Але коли одна з полиць знаходиться занадто високо, замовнику важливо яким книжкам на ній розташовані. У цьому випадку відповідь буде такою ж, як в попередній задачі - 155117520 способів, тому що першу полку заповнюємо вибірками-поєднаннями з 30 по 15, а на другу поміщаємо інші 15 книг без урахування перестановок.
Отже, бувають такі формулювання завдань, що відповіді можуть виходити неоднозначними. Для точного рішення потрібна додаткова інформація, яку ми зазвичай отримуємо з контексту ситуації. Творці екзаменаційних завдань, як правило, не допускають подвійного тлумачення умови задачі, формулюють його трохи довший. Однак, якщо у вас є сумніви, краще звернутися з питанням до викладача.
Сполучення і теорія ймовірностей.
У теорії ймовірностей завдання на поєднання зустрічаються найчастіше, тому що угруповання без порядку проходження важливіше саме для нерозпізнаних елементів. Якщо якісь елементи істотно розрізняються між собою, їх важко вибрати випадково, є орієнтири для невипадкового вибору.
завдання 8.
На книжковій полиці знаходиться зібрання творів одного автора в 6 томах. Книги однаково оформлені і розташовані в довільному порядку. Читач бере навмання 3 книги. Яка ймовірність того, що він взяв перші три томи?
Рішення.
Подія A - у читача перші три томи. Це 1-й, 2-й і 3-й томи. Без урахування порядку, в якому він вибирав книги, а тільки за кінцевим результатом, він міг взяти їх одним способом. Число сприятливих елементарних подій - 1.
Загальна кількість можливих елементарних подій дорівнює числу груп з 6-ти по 3, утворених без урахування порядку проходження елементів в групі, тобто дорівнює числу сполучень З 6 3 \u003d 6! / 3! / (6 - 3)! \u003d 4 · 5 · 6 / (1 · 2 · 3) \u003d 4 · 5 \u003d 20.
P (A) \u003d 1/20 \u003d 0,05.
відповідь: 0,05.
Порівняйте цю задачу з завданням 5 (на розміщення). В обох задачах дуже схожі умови і зовсім однакові відповіді. По-суті, це просто одна і та ж побутова ситуація і, відповідно, одна і та ж завдання, яке можна трактувати так чи інакше. Головне, щоб при підрахунку елементарних подій, як сприяють, так і всіх можливих, було одне й те саме розуміння ситуації.
Заключні зауваження.
Для суворого виведення всіх формул (який я тут не приводила) використовуються два основних правила комбінаторики:
правило множення
(Правило « і»). Згідно з ним, якщо елемент A можна вибрати n способами, і при будь-якому виборі A елемент B можна вибрати m способами, то пару A і B можна вибрати n · m
способами.
Це правило узагальнюється на довільну довжину послідовності.
правило складання
(Правило « або»). Воно стверджує, що, якщо елемент A можна вибрати n способами, а елемент B можна вибрати m способами, то вибрати A або B можна n + m
способами.
Ці правила потрібні і для вирішення завдань.
поняття факторіал також поширюється на нуль: 0! = 1 , Так як вважається, що порожня множина можна впорядкувати єдиним способом.
Обчислювати факторіали великих чисел прямим множенням на калькуляторі дуже довго, а дуже великих чисел - і на комп'ютері нешвидко. А як же справлялися з цим до створення комп'ютерів і калькуляторів? Ще на початку 18-го століття Дж.Стірлінгом і незалежно від нього А.Муавром була отримана формула для наближеного обчислення факториалов, яка тим точніше, чим більше число n. Зараз ця формула називається формулою Стірлінга:
Заключна завдання.
При вирішенні завдань з теорії ймовірностей з застосуванням методів комбінаторики необхідно ретельно аналізувати пропоновану ситуацію, щоб правильно вибрати тип вибірки. Спробуйте зробити це на прикладі наступної задачі. Вирішіть її, порівняйте відповідь, а потім натисніть кнопку, щоб відкрити моє рішення.
завдання 9.
З акваріума, в якому 6 сазанів і 4 коропа, сачком виловили 5 риб. Яка ймовірність того, що серед них виявиться 2 сазана і 3 коропа?
Рішення.
Елементарне подія - "в сачки група з 5 риб". Подія A - "серед 5 спійманих риб виявилося 3 коропа і 2 сазана ".
нехай n - загальне число всіх можливих елементарних подій, воно дорівнює числу способів згрупувати по 5 риб. Всього риб в акваріумі 6 + 4 \u003d 10. У процесі лову сачком риби зовні невиразні. (Ми не знаємо, виловили ми рибу на ім'я Баська або по імені Коська. Більш того, поки ми не витягли сачок наверх і не заглянули в нього, ми навіть не знаємо сазан це або короп.) Таким чином, "виловити 5 риб з 10 "означає зробити вибірку типу поєднання з 10 по 5.
n = З 10 5 = 10!/5!/(10 - 5)!
Витягнувши сачок і заглянувши в нього, ми можемо визначити котрий сприяє це результат чи ні, тобто чи перебуває улов з двох груп - 2 сазана і 3 коропа?
Група сазанів могла сформуватися вибором з 6 сазанів по 2. Причому все одно, хто з них першим забрався в сачок, а хто другим, таким чином це вибірка типу поєднання з 6 по 2. Позначимо загальне число таких вибірок m 1 і обчислимо його.
m 1 = З 6 2 = 6!/2!/(6 - 2)!
Аналогічно загальне число можливих груп по 3 коропа визначається числом сполучень з 4 по 3. Позначимо його m 2.
m 2 = З 4 3 = 4!/3!/(4 - 3)!
Групи коропів і сазанів формуються в сачки незалежно один від одного, тому для підрахунку числа елементарних подій, що сприяють події A, використовуємо правило множення ( "і" -правий) комбінаторики. Отже, загальне число сприятливих елементарних подій
m \u003d m 1 · m 2 = З 6 2· З 4 3
Імовірність події А визначаємо за формулою P (A) \u003d m / n \u003d З 6 2 × З 4 3 / З 10 5
Підставляємо в цю формулу всі значення, розписуємо факторіали, скорочуємо дріб і отримуємо відповідь:
P (A) \u003d 6! · 4! · 5! · (10 - 5)! / 2! / (6 - 2)! / 3! / (4 - 3)! / 10! \u003d 5/21 ≈ 0,238
Зауваження.
1) Сполучення зазвичай зустрічаються в задачах, де не важлива процес формування групи, а важливий тільки результат. Сазанові Басько без різниці першим він потрапив в сачок або останнім, але йому дуже важливо, в якій групі він виявився в результаті - серед тих, хто в сачки, або серед тих, хто на волі.
2) Зверніть увагу, ми використовуємо "і-правило", тому що союз "і" стоїть безпосередньо в описі події А, для якого потрібно обчислити ймовірність спільного улову двох груп. Однак, застосовуємо його тільки після того, як переконалися в незалежності вибірок. Справді, не може ж сазан, підпливаючи до сачки, перерахувати там своїх побратимів, і сказати Карпу: "Твоя чергу, наших там вже двоє". Та й чи погодиться короп лізти в сачок на догоду сазанові? Але якби вони могли домовитися, то це правило застосовувати було б уже не можна. Треба було б звернутися до поняття умовна ймовірність.
відповідь: 0,238.
Показати рішення.
Якщо ви випускник школи і будете здавати ЄДІ, то після вивчення цього розділу, поверніться (10 для базового і 4 для профільного рівнів ЄДІ 2020 по математиці), які можна вирішувати з використанням елементів комбінаторики і без неї (наприклад, на кидання монети). Який з можливих способів вирішення завдання подобається вам більше тепер?
А якщо ви хочете ще трохи потренуватися у вирішенні завдань комбінаторики, щоб навчитися швидко визначати тип вибірки і знаходити потрібні формули, то перейдіть на сторінку
Друзі! Раз вже є у мене цей мертвий блокнот, використовую-ка я його для того, щоб задати вам завдання, над якою вчора билося три фізика, два економіста, один політеховскій і один гуманітарій. Ми зламали собі весь мозок і у нас постійно виходять різні результати. Може бути, серед вас є програмісти і математичні генії, до того ж, завдання взагалі шкільна і дуже легка, у нас просто не виводиться формула. Тому що ми кинули заняття точними науками і замість цього чомусь пишемо книги і малюємо картини. Вибачте.
Отже, передісторія.
Мені видали нову банківську картку і я, як водиться, граючи вгадала її пін-код. Але не підряд. У сенсі, припустимо, пін-код був 8794, а я назвала 9748. Тобто, я тріумфально вгадала всі цифри, Яке містилися в даному чотиризначному числі. Ну так, не саме число, А просто його складові угадала. Але цифри-то все вірні! ПРИМІТКА - я діяла навмання, тобто, мені не треба було розставити вже відомі числа в потрібному порядку, я просто діяла в дусі: ось тут є невідомі мені чотири цифри, і я вважаю, що серед них можуть бути 9, 7, 4 і 8, а порядок їх не важливий. Ми тут же задалися питанням, скільки у мене взагалі було варіантів (Напевно, щоб зрозуміти, наскільки це круто, що я ось взяла і вгадала). Тобто, зі скількох комбінацій чотирьох цифр мені потрібно було вибирати? І тут, натурально, почалося пекло. У нас весь вечір вибухала голова, і у всіх, в результаті, вийшли абсолютно різні варіанти відповіді! Я навіть почала виписувати всі ці комбінації в блокнот поспіль у міру зростання, але на чотирьох сотнях зрозуміла, що їх більше чотирьох сотень (у всякому разі, це спростувало відповідь фізика треш, який запевняв мене, що комбінацій чотири сотні, але все одно це не зовсім однозначно) - і здалася.
власне, сутність питання. Яка ймовірність вгадування (в будь-якому порядку) чотирьох чисел, що містяться в чотиризначному числі?
Чи ні, формулюємо (я гуманітарій, вибачте, хоча до математики завжди живила величезну слабкість), щоб було ясніше і чіткіше. скільки не повторюються комбінацій цифр міститься в ряду порядкових числівників від 0 до 9999? ( будь ласка, не плутайте це з питанням "скільки комбінацій не повторюютьсяцифр "!!! цифри можуть повторюватися! в сенсі, 2233 і 3322 - це в даному випадку одна і та ж комбінація !!).
Або ще конкретніше. Мені потрібно чотири рази вгадати одну цифру з десяти. Але не підряд.
Ну або ще як-небудь. Загалом, потрібно дізнатися, скільки у мене було варіантів числовий комбінації, з якої складався пін-код картки. Допоможіть, люди добрі! Тільки, будь ласка, допомагаючи, не починайте відразу писати, що варіантів цих 9999 (Вчора таке всім приходило в голову спочатку), тому що це ж дурниці - адже в тому ракурсі, який нас хвилює, число 1234, число 3421, число 4312 і так далі є одним і тим же! Ну і так, цифри можуть повторюватися, адже буває пін-код 1111 або там, наприклад, 0007. Можна уявити замість пін-коду номер машини. Припустимо, яка ймовірність вгадати всі однозначні цифри, з яких складається номер машини? Або, щоб взагалі прибрати теорію ймовірності - зі скількох числових комбінацій мені потрібно було вибрати одну?
Будь ласка, підкріпите свої відповіді і міркування якимись точними формулами, тому що ми вчора і так мало не втрачали. Заздалегідь всім велике спасибі!
P.S. Один розумний чоловік, програміст, художник і винахідник, тільки що дуже вірно підказав правильне рішення проблеми, подарувавши мені кілька хвилин прекрасного настрою: " рішення задачі таке: у неї обсесивно-комп ульсівное розлад, лікування таке: заміж і підгортати помідори. мене б більше на її місці хвилювало не питання «наскільки ймовірним є», а питання «схуя я звертаю увагу на всі ці цифри»? В общем-то, навіть нічого додати :)
Калькулятор нижче призначений для генерації всіх сполучень з n по m елементів.
Число таких поєднань, як можна розрахувати за допомогою калькулятора Елементи комбінаторики. Перестановки, розміщення, поєднання.
Опис алгоритму генерації під калькулятором.
алгоритм
Комбінації генеруються в лексикографічному порядку. Алгоритм працює з порядковими індексами елементів множини.
Розглянемо алгоритм на прикладі.
Для простоти викладу розглянемо безліч з п'яти елементів, індекси в якому починаються з 1, а саме, 1 2 3 4 5.
Потрібно згенерувати всі комбінації розміру m \u003d 3.
Спочатку Ініціалізація перша комбінація заданого розміру m - індекси в порядку зростання
1 2 3
Далі перевіряється останній елемент, т. Е. I \u003d 3. Якщо його значення менше n - m + i, то він инкрементируется на 1.
1 2 4
Знову перевіряється останній елемент, і знову він инкрементируется.
1 2 5
Тепер значення елемента дорівнює максимально можливому: n - m + i \u003d 5 - 3 + 3 \u003d 5, перевіряється попередній елемент з i \u003d 2.
Якщо його значення менше n - m + i, то він инкрементируется на 1, а для всіх наступних за ним елементів значення прирівнюється до значення попереднього елемента плюс 1.
1 (2+1)3 (3+1)4 = 1 3 4
Далі знову йде перевірка для i \u003d 3.
1 3 5
Потім - перевірка для i \u003d 2.
1 4 5
Потім настає черга i \u003d 1.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
І далі,
2 3 5
2 4 5
3 4 5
- Останнім поєднання, так як всі його елементи рівні n - m + i.
Незважаючи на важливу роль PIN-кодів в світовій інфраструктурі, до сих пір не проводилося академічних досліджень про те, як, власне, люди вибирають PIN-коди.
Дослідники з університету Кембриджу Sören Preibusch і Ross Anderson виправили ситуацію, опублікувавши перший в світі кількісний аналіз складності вгадування 4-ціферний банківського PIN-коду.
Використовуючи дані про витік паролів з небанківських джерел і онлайн анкетування, вчені з'ясували, що до вибору PIN-кодів користувачі ставляться набагато серйозніше, ніж до вибору паролів для веб-сайтів: більшість кодів містять практично випадковий набір цифр. Проте, серед вихідних даних присутні і прості комбінації, і дні народження, - тобто, при деякому везінні зловмисник може просто вгадати заповітний код.
Відправною точкою дослідження був набір 4-ціферний послідовностей в паролі з бази RockYou (1.7 млн), і бази з 200 тисяч PIN-кодів від програми блокування екрану iPhone (базу надав розробник програми Daniel Amitay). У графіках, побудованих за цими даними, проступають цікаві закономірності - дати, року, повторювані цифри, і навіть PIN-коди, що закінчуються на 69. На основі цих спостережень вчені побудували лінійну регресійну модель, яка оцінює популярність кожного PIN-коду в залежності від 25 чинників, - наприклад, чи є код датою в форматі ДДММ, чи є він зростаючої послідовністю, і так далі. Цим загальним умовам відповідають 79% і 93% PIN-кодів в кожному з наборів.
Отже, користувачі вибирають 4-ціферние коди на основі всього декількох простих факторів. Якби так вибиралися і банківські PIN-коди, 8-9% з них можна було б вгадати всього за три спроби! Але, звичайно, до банківських кодами люди ставляться набагато уважніше. Зважаючи на відсутність скільки-небудь великого набору справжніх банківських даних, дослідники опитали понад 1300 осіб, щоб оцінити, наскільки реальні PIN-коди відрізняються від вже розглянутих. З огляду на специфіку дослідження, у респондентів запитували, чи не про самих кодах, а тільки про їх відповідність будь-якого з вищеназваних факторів (зростання, формат ДДММ, і т.д.).
Виявилося, що люди дійсно набагато ретельніше вибирають банківські PIN-коди. Приблизно чверть опитаних використовують випадковий PIN, згенерований банком. Більше третини вибирають свій PIN-код, використовуючи старий номер телефону, номер студентського квитка, або інший набір цифр, який виглядає випадковим. Згідно з отриманими результатами, 64% власників карт використовують псевдовипадковий PIN-код, - це набагато більше, ніж 23-27% в попередніх експериментах з не-банківськими кодами. Ще 5% використовують цифровий патерн (наприклад, 4545), а 9% вважають за краще патерн на клавіатурі (наприклад, 2684). В цілому, зловмисник з шістьма спробами (три з банкоматом і три з платіжним терміналом) має менше 2% шансів вгадати PIN-код чужий карти.
| фактор | приклад | RockYou | iPhone | Опитування |
|---|---|---|---|---|
| дати | ||||
| ДДММ | 2311 | 5.26 | 1.38 | 3.07 |
| ДМГГ | 3876 | 9.26 | 6.46 | 5.54 |
| ММДД | 1123 | 10.00 | 9.35 | 3.66 |
| ММГГ | 0683 | 0.67 | 0.20 | 0.94 |
| РРРР | 1984 | 33.39 | 7.12 | 4.95 |
| Разом | 58.57 | 24.51 | 22.76 | |
| клавіатурний патерн | ||||
| суміжні | 6351 | 1.52 | 4.99 | - |
| квадрат | 1425 | 0.01 | 0.58 | - |
| кути | 9713 | 0.19 | 1.06 | - |
| хрест | 8246 | 0.17 | 0.88 | - |
| діагональна лінія | 1590 | 0.10 | 1.36 | - |
| горизонтальна лінія | 5987 | 0.34 | 1.42 | - |
| слово | 5683 | 0.70 | 8.39 | - |
| вертикальна лінія | 8520 | 0.06 | 4.28 | - |
| Разом | 3.09 | 22.97 | 8.96 | |
| цифровий патерн | ||||
| закінчується на 69 | 6869 | 0.35 | 0.57 | - |
| тільки цифри 0-3 | 2000 | 3.49 | 2.72 | - |
| тільки цифри 0-6 | 5155 | 4.66 | 5.96 | - |
| повторювані пари | 2525 | 2.31 | 4.11 | - |
| однакові цифри | 6666 | 0.40 | 6.67 | - |
| спадна послідовність | 3210 | 0.13 | 0.29 | - |
| зростаюча послідовність | 4567 | 3.83 | 4.52 | - |
| Разом | 15.16 | 24.85 | 4.60 | |
| Випадковий набір цифр | 23.17 | 27.67 | 63.68 | |
Все б добре, але, на жаль, значна частина опитаних (23%) вибирає PIN-код у вигляді дати, - і майже третина з них використовує дату свого народження. Це істотно змінює справу, адже майже всі (99%) респонденти відповіли, що зберігають в гаманці з банківськими картами різні посвідчення особи, на яких ця дата надрукована. Якщо зловмисник знає день народження власника карти, то при грамотному підході ймовірність вгадування PIN-коду злітає до 9%.
100 найпопулярніших PIN-кодів
0000, 0101-0103, 0110, 0111, 0123, 0202, 0303, 0404, 0505, 0606, 0707, 0808, 0909, 1010, 1101-1103, 1110-1112, 1123, 1201-1203, 1210-1212, 1234, 1956-2015, 2222, 2229, 2580, 3333, 4444, 5252, 5683, 6666, 7465, 7667.
P.S. На практиці, зрозуміло, зловмисникові набагато простіше підглянути ваш PIN-код, ніж вгадувати його. Але і від підглядання можна захиститися - навіть, здавалося б, в безвихідному становищі:
комбінаторики
Комбінаторика - розділ математики, який вивчає завдання вибору і розташування елементів з деякого основного безлічі відповідно до заданих правил. Формули і принципи комбінаторики використовуються в теорії ймовірностей для підрахунку ймовірності випадкових подій і, відповідно, отримання законів розподілу випадкових величин. Це, в свою чергу, дозволяє досліджувати закономірності масових випадкових явищ, що є дуже важливим для правильного розуміння статистичних закономірностей, що виявляються в природі і техніці.
Правила додавання і множення в комбінаториці
Правило суми. Якщо два дії А і В взаємно виключають одна одну, причому дія А можна виконати m способами, а В - n способами, то виконати одну одну з таких дій (або А, або В) можна n + m способами.
Приклад 1.
У класі навчається 16 хлопчиків і 10 дівчаток. Скількома способами можна призначити одного чергового?
Рішення
Черговим можна призначити або хлопчика, або дівчинку, тобто черговим може бути будь-який з 16 хлопчиків, або будь-яка з 10 дівчаток.
За правилом суми отримуємо, що одного чергового можна призначити 16 + 10 \u003d 26 способами.
Правило твори. Нехай потрібно виконати послідовно k дій. Якщо перша дія можна виконати n 1 способами, друга дія n 2 \u200b\u200bспособами, третє - n 3 способами і так до k-го дії, яке можна виконати n k способами, то всі k дій разом можуть бути виконані:
способами.
Приклад 2.
У класі навчається 16 хлопчиків і 10 дівчаток. Скількома способами можна призначити двох чергових?
Рішення
Першим черговим можна призначити або хлопчика, або дівчинку. Оскільки в класі вчиться 16 хлопчиків і 10 дівчаток, то призначити першого чергового можна 16 + 10 \u003d 26 способами.
Після того, як ми вибрали першого чергового, другого ми можемо вибрати з решти 25 осіб, тобто 25-ю способами.
По теоремі множення двоє чергових можуть бути обрані 26 * 25 \u003d 650 способами.
Сполучення без повторень. Сполучення з повтореннями
Класичною завданням комбінаторики є завдання про кількість сполучень без повторень, зміст якої можна висловити питанням: скількома способами можна, можливо вибрати m з n різних предметів?
Приклад 3.
Необхідно вибрати в подарунок 4 з 10 наявних різних книг. Скількома способами можна це зробити?
Рішення
Нам з 10 книг потрібно вибрати 4, причому порядок вибору не має значення. Таким чином, потрібно знайти число поєднань з 10 елементів по 4:
.
Розглянемо задачу про число поєднань з повтореннями: є по r однакових предметів кожного з n різних типів; скількома способами можна, можливо вибрати m () з цих (N * r) предметів?
.
Приклад 4.
У кондитерському магазині продавалися 4 сорти тістечок: наполеони, еклери, пісочний і листкові. Скількома способами можна купити 7 тістечок?
Рішення
Оскільки серед 7 тістечок можуть бути тістечка одного сорту, то число способів, якими можна купити 7 тістечок, визначається числом сполучень з повтореннями з 7 по 4.
.
Розміщення без повторень. Розміщення з повтореннями
Класичною завданням комбінаторики є завдання про кількість розміщень без повторень, зміст якої можна висловити питанням: скількома способами можна, можливо вибрати і розмістити по m різним місцях m з n різних предметів?
Приклад 5.
В деякій газеті 12 сторінок. Необхідно на сторінках цієї газети помістити чотири фотографії. Скількома способами можна це зробити, якщо жодна сторінка газети не повинна містити більше однієї фотографії?
Рішення.
У цьому завданню ми не просто обираємо фотографії, а розміщуємо їх на певних сторінках газети, причому кожна сторінка газети повинна містити не більше однієї фотографії. Таким чином, завдання зводиться до класичної задачі про визначення числа розміщень без повторень з 12 елементів по 4 елементи:
Таким чином, 4 фотографії на 12 сторінках можна розташувати 11880 способами.
Також класичної завданням комбінаторики є завдання про кількість розміщень з повтореннями, зміст якої можна висловити питанням: скількома способами можна, можливо вибрать і розмістити по m різним місцях m з n предметів, зреді яких є однакові?
Приклад 6.
У хлопчика залишилися від набору для настільної гри штампи з цифрами 1, 3 і 7. Він вирішив за допомогою цих штампів нанести на все книги п'ятизначні номери-скласти каталог. Скільки різних п'ятизначних номерів може скласти хлопчик?
Перестановки без повторень. Перестановки з повтореннями
Класичною завданням комбінаторики є завдання про кількість перестановок без повторення, зміст якої можна висловити питанням: скількома способами можна, можливо розмістити n різних предметів на n різних місцях?
Приклад 7.
Скільки можна скласти чотирибуквеними «слів» з букв слова «шлюб»?
Рішення
Генеральною сукупністю є 4 літери слова «шлюб» (б, р, а, к). Число «слів» визначається перестановками цих 4 букв, т. Е.
Для випадку, коли серед обираних n елементів є однакові (вибірка з поверненням), завдання про кількість перестановок з повтореннями можна виразити питанням: скількома способами можна переставити n предметів, розташованих на n різних місцях, якщо серед n предметів є k різних типів (k< n), т. е. есть одинаковые предметы.
Приклад 8.
Скільки різних буквосполучень можна зробити з букв слова «Міссісіпі»?
Рішення
Тут 1 буква «м», 4 букви «і», 3 літери «c» і 1 буква «п», всього 9 букв. Отже, число перестановок з повтореннями одно
ОПОРНИЙ КОНСПЕКТ ПО ПОДІЛУ "комбінаторики"