Розв'язник вправ по дискретній математиці/Комбінаторика/Перестановки
Розв'язник вправ по дискретній математиці. Комбінаторика. Перестановки
ред.Для кращого розуміння краще ознайомитись комбінаторика, перестановки.
Приклад
ред.Умова
ред.- Скількома способами можна витягнути 5 карт з колоди, якщо
- а) важливий порядок в якому їх діставати,
- б) порядок не важливий.
Розв'язання
ред.Позначимо першу кількість , а другу . Спочатку знайдемо відповідь для першої умови, коли порядок має значення. Скористаємось тим, що
- Кількість розміщень множини з елементів по елементів можна обчислити за формулою .
Тоді кількість варіантів може бути обчислена як кількість розміщень без повторень: (варіантів).
Тепер знайдемо відповідь на другу частину умови. Нам потрібно розуміти, що наша попередня відповідь (представивши її як множину поодиноких відповідей)
включає в себе і множину відповідей на дане запитання, бо враховує ті ж комбінації карт, але вибрані в іншому порядку.
Отже, якщо ми виключимо непотрібні нам варіанти з попереднього розв'язку то знайдемо потрібний нам. Скористаємось для цього формулою для розрахунку
кількості перестановок для множини з n елементів . Тоді не важко здогадатись, що шукана кількість це
Така формула записується як кількість сполук: .
Отже (варіантів).
Якою кількістю способів з колоди в 36 карт можна вибрати невпорядкований набір з 5 карт, так, щоб в ньому напевно були: 1туз, 1валет, 1карта червоної масті?
Розв'язання:
Всього комбінацій туз-валет може бути 16(кожний туз із чотирьох мастей може бути с кожним валетом), враховуючи, що в наборі не може бути більше однієї червоної карти, то зі всього числа потрібно виключити варіанти з червоним тузом та червоним валетом. Таких комбінацій буде 4 (2чорних туза та 2 чорних валета)
Тепер роздивимось варінт, коли у наборі або червоний туз або червоний валет.
Таких комбінацій буде 8.
Так як червона карта вже вибрана,то 3 карти, що залишилися, повинні бути чорної масті. Карт для вибора буде 14 (18 чорних відняти чорні валети та тузи).
Тож третю карту можна вибрати 14ма способами, четверту - 13ма способами, а 5ту - 12ма способами.
Всього комбінацій (якщо або валет або туз - червоний) буде:
8*14*13*12=17472;
У нас залишаються варіанти чорний туз, чорний валет, таких комбінацій 4. Залишається обрати 3 карти: 1 червона(з 14ти, бо валета та туза ми вже обрали), 1 чорна(з 14ти) і ще одна чорна(з 13).
Таким чином, комбінацій(якщо і валет і туз чорні) буде:
4*14*14*13=10192;
Всього ж способів вибрати 5 карт, що задовільняють цим умовам:
17472+10192=27664.