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

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

Приклад

ред.

Умова

ред.
Скількома способами можна витягнути 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.