6.3 Комбинаторика

🔢 Основные правила

Правило суммы

Если объект A можно выбрать m способами, а объект B — n способами, причем A и B не пересекаются, то выбрать A или B можно m + n способами.

\[ N = m + n \]

m путей

+

n путей

Правило произведения

Если объект A можно выбрать m способами, а после каждого выбора A объект B можно выбрать n способами, то пару (A, B) можно выбрать m × n способами.

\[ N = m \times n \]

m вариантов

× n вариантов

Пример правила суммы: В меню 3 супа и 5 вторых блюд. Сколько вариантов выбора одного блюда?

3 + 5 = 8 вариантов

Пример правила произведения: Сколько двузначных чисел можно составить из цифр 1,2,3?

3 варианта для десятков × 3 варианта для единиц = 9 чисел

🔄 Перестановки

Упорядоченные наборы из n различных элементов.

\[ P_n = n! \]

где \( n! = 1 \times 2 \times 3 \times \dots \times n \) (n факториал)

A

B

C

ABC

ACB

BAC

BCA

CAB

CBA

Все перестановки для n=3: P₃ = 3! = 6

Перестановки с повторениями

Если есть одинаковые элементы (k одинаковых элементов одного типа):

\[ P_n(k_1, k_2, \dots) = \frac{n!}{k_1! \cdot k_2! \cdot \dots} \]

Сколько слов можно составить из букв «МАМА»?

n=4, буква «М» — 2 раза, «А» — 2 раза: \( P = \frac{4!}{2! \cdot 2!} = \frac{24}{4} = 6 \)

🔠 Размещения

Упорядоченные наборы из k элементов, выбранных из n различных элементов.

\[ A_n^k = \frac{n!}{(n-k)!} \]

1. Выбор первого элемента: n вариантов

2. Выбор второго: (n-1) вариант

3. …

k. Выбор k-го: (n-k+1) вариант

\( A_n^k = n \times (n-1) \times \dots \times (n-k+1) \)

1

2

3

4

12, 13, 14

21, 23, 24

31, 32, 34

41, 42, 43

Размещения из 4 по 2: A₄² = 4×3 = 12

🔣 Сочетания

Неупорядоченные наборы из k элементов, выбранных из n различных элементов (порядок не важен).

\[ C_n^k = \frac{n!}{k!(n-k)!} \]

Сочетания

Порядок не важен: {A,B} = {B,A}

\( C_n^k = \frac{A_n^k}{k!} \)

vs

Размещения

Порядок важен: (A,B) ≠ (B,A)

\( A_n^k = C_n^k \times k! \)

A

B

C

D

AB

AC

AD

BC

BD

CD

Сочетания из 4 по 2: C₄² = 6

① Пример 1: Перестановки

Сколькими способами 5 человек могут встать в очередь?

1.

Это перестановки 5 различных элементов

2.

\( P_5 = 5! = 1 \times 2 \times 3 \times 4 \times 5 = 120 \)

② Пример 2: Размещения

Сколько трёхзначных чисел можно составить из цифр 1,2,3,4 без повторений?

1.

Порядок важен (123 ≠ 321), поэтому размещения

2.

n=4 (цифры), k=3 (разряды)

3.

\( A_4^3 = 4 \times 3 \times 2 = 24 \)

③ Пример 3: Сочетания

Сколькими способами можно выбрать 2 книги из 5 различных книг?

1.

Порядок не важен (комбинации книг)

2.

n=5, k=2

3.

\( C_5^2 = \frac{5!}{2!(5-2)!} = \frac{120}{2 \times 6} = 10 \)

✅ Алгоритм решения задач

Определить, важен ли порядок элементов:
- Да → Размещения
- Нет → Сочетания
Проверить, все ли элементы используются:
- Да → Перестановки
Есть ли одинаковые элементы:
- Да → Перестановки с повторениями
Выбрать формулу и вычислить

Тип	Порядок важен	Формула	Пример
Перестановки	Да	\( P_n = n! \)	Очередь из n человек
Размещения	Да	\( A_n^k = \frac{n!}{(n-k)!} \)	Пароли, пин-коды
Сочетания	Нет	\( C_n^k = \frac{n!}{k!(n-k)!} \)	Выбор комитета, лотереи

✓ Сочетания всегда меньше или равны размещениям: \( C_n^k \leq A_n^k \)

✓ Помните, что \( C_n^k = C_n^{n-k} \) (выбрать k или исключить n-k)

Комбинаторика

🔢 Основные правила

🔄 Перестановки

🔠 Размещения

🔣 Сочетания

① Пример 1: Перестановки

② Пример 2: Размещения

③ Пример 3: Сочетания

✅ Алгоритм решения задач

Похожие записи

Геометрия

Вероятность и статистика

Множества и логика