Розв'язник вправ по дискретній математиці/Комбінаторика/Перестановки

Розв'язник вправ по дискретній математиці. Комбінаторика. Перестановки

Для кращого розуміння краще ознайомитись комбінаторика, перестановки.

Приклад

Умова

Скількома способами можна витягнути 5 карт з колоди, якщо

а) важливий порядок в якому їх діставати,

б) порядок не важливий.

Розв'язання

Позначимо першу кількість $N_{1}$, а другу $N_{2}$. Спочатку знайдемо відповідь для першої умови, коли порядок має значення. Скористаємось тим, що

Кількість розміщень множини з $n$ елементів по $m$ елементів можна обчислити за формулою $A_{n}^{m}={\frac {n!}{(n-m)!}}$.

Тоді кількість варіантів може бути обчислена як кількість розміщень без повторень: $N_{1}=A_{36}^{5}={\frac {36!}{(36-5)!}}={\frac {36*35*34*33*32*31!}{31!}}=36*35*34*33*32=45239040$ (варіантів).

Тепер знайдемо відповідь на другу частину умови. Нам потрібно розуміти, що наша попередня відповідь (представивши її як множину поодиноких відповідей)

включає в себе і множину відповідей на дане запитання, бо враховує ті ж комбінації карт, але вибрані в іншому порядку.

Отже, якщо ми виключимо непотрібні нам варіанти з попереднього розв'язку то знайдемо потрібний нам. Скористаємось для цього формулою для розрахунку

кількості перестановок для множини з n елементів $P_{n}=n!$. Тоді не важко здогадатись, що шукана кількість це

$N_{2}={\frac {A_{n}^{m}}{P_{m}}}$

Така формула записується як кількість сполук: $C_{n}^{m}={\frac {n!}{m!*(n-m)!}}$.

Отже $N_{2}=C_{n}^{m}={\frac {36!}{5!*(36-5)!}}={\frac {36*35*34*33*32*31!}{5!*31!}}=9*7*34*11*16=376922$ (варіантів).

Якою кількістю способів з колоди в 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.