Елементи комбінаторики, теорія і приклади рішень завдань з комбінаторики
Спасибі, що Новомосковскете і діліться з іншими
розміщення
Розглянемо деякий безліч $ Х $, що складається з $ n $ елементів $ X = \
Розміщенням з $ n $ елементів безлічі $ Х $ по $ k $ елементам назвемо будь-який упорядкований набір $ \ left (x_, x_. X_ \ right) $ елементів безлічі $ Х $.
Якщо вибір елементів безлічі $ Y $ з $ Х $ відбувається з поверненням, тобто кожен елемент безлічі $ Х $ може бути обраний кілька разів, то число розміщень з $ n $ по $ k $ знаходиться за формулою $ n ^ k $ (розміщення з повтореннями).
Если же выбор делается без возвращения, т.е. кожен елемент безлічі $ Х $ можна вибирати тільки один раз, то кількість розміщень з $ n $ по $ k $ позначається $ A_n ^ k $ і визначається рівністю $$ A_n ^ k = n \ cdot (n-1) \ cdot. \ Cdot (n-k + 1) = \ frac. $$ (розміщення без повторень).
Приклад. Нехай дано шість цифр: 1; 2; 3; 4; 5; 6. Визначити скільки тризначних чисел можна скласти з цих цифр.
Рішення. Если цифры могут повторяться, то количество трехзначных чисел будет $m=n^k=6^3=216$. Якщо цифри не повторюються, то $ m = A_6 ^ 3 = 6 \ cdot 5 \ cdot 4 = 120 $.
Приклад. Студенти інституту вивчають в кожному семестрі по десять дисциплін. У розклад занять включаються кожен день по 3 дисципліни. Скільки різних розкладів може скласти диспетчерська?
Рішення. Розклад на кожен день може відрізнятися або предметами, або порядком розташування цих предметів, тому маємо розміщення: $ A_ ^ 3 = 10 \ cdot 9 \ cdot 8 = 720 $.
перестановки
Окремий випадок розміщення при $ n = k $ називається перестановкою з $ n $ елементів. Число всех перестановок из $n$ элементов равно $A_n^n=P_n=n!$.
Нехай тепер з безлічі $ Х $ вибирається невпорядковане підмножина $ Y $ (порядок елементів в підмножині не має значення). Поєднаннями з $ n $ елементів по $ k $ називаються підмножини з $ k $ елементів, що відрізняються один від одного хоча б одним елементом. Загальна кількість всіх сполучень з $ n $ по $ k $ позначається $ C_n ^ k $ і так само $$ C_n ^ k = \ frac = \ frac = \ frac. $$
Справедливы равенства: $$ C_n^0=1, \; C_n ^ n = 1, \; C_n ^ k = C_n ^. $$
Приклад. У групі з 27 студентів потрібно вибрати трьох чергових. Скількома способами можна це зробити?
Рішення. Так як порядок студентів не важливий, використовуємо формулу для числа сполучень: $$ C_ ^ 3 = \ frac = \ frac = 2925. $$
Подробиці і онлайн калькулятори для комбінаторики
Ще наочно з картинками і прикладами про основні формули комбінаторики (розміщення, перестановки, поєднання) і їх застосування для вирішення завдань тут: Формули комбінаторики. Для швидкого знаходження значень - онлайн-калькулятори:
Правила суми і твори
Правило суми. Якщо деякий об'єкт $ А $ може бути обраний із сукупності об'єктів $ m $ способами, а інший об'єкт $ В $ може бути обраний $ n $ способами, то вибрати або $ А $, або $ В $ можна $ m + n $ способами.
Правило твори. Якщо об'єкт $ А $ можна вибрати з сукупності об'єктів $ m $ способами і після кожного такого вибору об'єкт $ В $ можна вибрати $ n $ способами, то пара об'єктів $ (А, В) $ в зазначеному порядку може бути обрана $ m \ cdot n $ способами.
Приклад. Наряд студентки складається з блузки, спідниці і туфель. Дівчина має в своєму гардеробі чотири блузки, п'ять спідниць і троє туфель. Скільки нарядів може мати студентка?
Рішення. Нехай спочатку студентка вибирає блузку. Цей вибір може бути здійснений чотирма способами, так як студентка має чотири блузки, потім п'ятьма способами відбудеться вибір спідниці і трьома способами вибір туфель. За принципом множення виходить 4 * 5 * 3 = 60 нарядів (комбінацій).
Ми вирішимо ваші завдання з теорії ймовірностей