Перестановка, комбінація, розміщення
Терміни
- Перестановка – це розміщення елементів у фіксованому порядку.
- Комбінація (k елементів) – це вибір k елементів із заданої множини.
- Комбінація з повторенням (k елементів) – це вибір k елементів із заданої множини, причому елементи можуть повторюватися.
- Варіація (k елементів) – це впорядкований вибір k елементів із заданої множини.
- Варіація з повторенням (k елементів) – це впорядкований вибір k елементів із заданої множини, причому елементи можуть повторюватися.
Приклади
| перестановка | \{A, B, C\} | ABC, ACB, BAC, BCA, CAB, CBA |
| комбінація | \{A, B, C, D\}; k=2 | AB, AC, AD, BC, BD, CD |
| комбінація з повторенням | \{A, B, C, D\}; k=2 | AA, AB, AC, AD, BB, BC, BD, CC, CD, DD |
| варіація | \{A, B, C, D\}; k=2 | AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC |
| варіація з повторенням | \{A, B, C\}; k=2 | AA, AB, AC, BA, BB, BC, CA, CB, CC |
Формули
Кількість перестановок, комбінацій та варіацій наведено в наступній таблиці:
| кількість усіх перестановок n елементів | n! |
| кількість усіх k-елементних комбінацій з n елементів | \binom{n}{k} = \frac{n!}{(n-k)!k!} |
| кількість усіх k-елементних комбінацій з повторенням з n елементів | \binom{n + k - 1}{k} |
| кількість усіх k-елементних варіацій з n елементів | \frac{n!}{(n-k)!} |
| кількість усіх k-елементних варіацій з повторенням з n елементів | n^k |
Біноміальний коефіцієнт
Комбінаторне число вказує на кількість комбінацій, тобто способів, як вибрати k елементів із множини з n елементів. Комбінаторні числа дуже часто зустрічаються в комбінаторних обчисленнях, тому мають спеціальне позначення \binom{n}{k} (читаємо „n над k“).
Для n \geq k \geq 0 виконується формула: \binom{n}{k} = \frac{n!}{k!(n-k)!}
Для комбінаторних чисел існує ряд інших співвідношень, наприклад:
- \binom{n}{k} = \binom{n}{n-k}
- \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}
- \sum_{k=0}^n \binom{n}{k} = 2^n
Приклади:
| \binom{3}{1} | = 3 |
| \binom{4}{2} | = 6 |
| \binom{5}{3} | = 10 |
| \binom{6}{2} | = 15 |
| \binom{15}{15} | = 1 |
