Шпаргалки / Математика / Школа / Дискретная математика

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

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

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

N=n\cdot m

Математически — это декартово произведение множеств:

|A \times B| = |A| \cdot |B|

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

Пусть некоторый объект A можно выбрать $$n$$ различными способами, а другой объект B можно выбрать $$m$$ способами. Тогда существует $$n+m$$ способов выбрать либо объект A, либо объект B.

\[ N=n+m \]

Математически — это объединение непересекающихся множеств:

|A \cup B| = |A| + |B| \quad \text{(если } A \cap B = \emptyset\text{)}

Если множества пересекаются:

|A \cup B| = |A| + |B| - |A \cap B|

Комбинаторные принципы

Принцип Дирихле (Pigeonhole Principle)

Если $$n$$ объектов разложить по $$m$$ ящикам, и $$n > m$$ , то хотя бы в одном ящике окажется не менее двух объектов.

Применение: доказательства существования, минимальные условия.
Пример: 13 носков в 12 ящиках → в одном ящике как минимум 2 носка.

Принцип включения-исключения

Позволяет корректно посчитать количество элементов в объединении пересекающихся множеств.

|A_1 \cup A_2 \cup \dots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \dots + (-1)^{n+1} |A_1 \cap \dots \cap A_n|

Обратные задачи (Complimentary Counting)

Иногда проще посчитать обратное событие и вычесть из общего числа:

\text{количество способов} = \text{общее количество} - \text{неподходящие варианты}

Пример: сколько чисел от 1 до 100 не делятся на 3? → $100 - \lfloor 100/3 \rfloor = 100 - 33 = 67$ .

Принцип умножения (Rule of Product)

Если выбор состоит из нескольких последовательных шагов, общее число способов:

N = n_1 \cdot n_2 \cdot \dots \cdot n_k

Пример: выбрать футболку (3 варианта) и штаны (4 варианта) → $3\cdot 4 = 12$ .

Принцип сложения (Rule of Sum)

Если нужно выбрать либо один объект, либо другой, и множества не пересекаются:

\[ N = n_1 + n_2 \]

Если множества пересекаются, вычитаем пересечение:

N = n_1 + n_2 - |A_1 \cap A_2|

Перестановки (Permutations)

\[ P_n=n! \]

Пример задачи:
Какое число способов существует для расположения 4 книг на полке?

Решение:

\[ P_4=4!=24 \]

С повторениями

P_n^{(k_1, k_2, \dots, k_m)} = \frac{n!}{k_1! \, k_2! \, \dots \, k_m!}

Пример задачи:
Сколько способов расположить буквы в слове “КОЛОКОЛ”?

Решение:
Буквы “О” повторяются 3 раза, “К” - 2 раза, “Л” - 2 раза:

P_7^{(3,2,2)}=\frac{7!}{3!2!2!}=420

Размещения (Arrangements)

A_n^k=n\cdot (n-1) \cdot (n-2) \cdot \dots.\cdot (n-k+1)=\frac{n!}{(n-k)!}, \quad 0 \le k \le n

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

Решение:

A_4^3=\frac{4!}{(4-3)!}=24

С повторениями

\[ A_n^k=n^k \]

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

Решение:

\[ 4^3=64 \]

Сочетания (Combinations)

С_n^k=\frac{n!}{k!(n-k)!}, \quad 0 \le k \le n

Пример задачи:
Сколькими способами из группы из 10 человек можно сформировать команду из 3 человек?

Решение:

C_{10}^3=\frac{10!}{3!7!}=120

С повторениями

С_n^k=\frac{(n+k-1)!}{k!(n-1)!}

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

Решение:

C_5^7=\frac{(5+7-1)!}{7!(5-1)!}=\frac{11!}{4!7!}=330

Для запоминания

P (перестановки) — все разные, порядок важен → факториал
A (размещения)— берём часть, порядок важен → **делим на $$(n-k)!$$
C (сочетания) — берём часть, порядок не важен → ещё делим на $$k!$$
С повторениями — значит, можно больше вариантов → прибавляем или возводим в степень