Шпаргалка по комбинаторике и упрощению вычислений

Для быстрого решения задач используйте базовые формулы: число перестановок $P_n = n!$, размещений $A_n^k = \frac{n!}{(n-k)!}$ и сочетаний $C_n^k = \frac{n!}{k!(n-k)!}$. При вычислениях дробей с факториалами или большими числами применяйте правило сокращения общих множителей до начала умножения, чтобы избежать работы с громоздкими значениями. Ниже приведены подробные таблицы, примеры применения и алгоритмы упрощения выражений.

Основы комбинаторики: когда какую формулу применять

Комбинаторика отвечает на вопрос «сколькими способами?». Выбор формулы зависит от двух факторов: важен ли порядок элементов и могут ли элементы повторяться.

1. Перестановки (Порядок важен, все элементы участвуют)

Используется, когда нужно расположить все $n$ элементов по местам.

• Без повторений: $P_n = n!$
  • Пример: Сколькими способами можно расставить 5 книг на полке? Ответ: $5! = 120$.
• С повторениями: Если среди $n$ элементов есть одинаковые (группы по $n_1, n_2, \dots$), формула: $$ P = \frac{n!}{n_1! \cdot n_2! \cdot \dots \cdot n_r!} $$
  • Пример: Сколько разных слов можно составить из букв слова «БАНАН»? (3 буквы «А», 2 буквы «Н», 1 «Б»). Ответ: $\frac{5!}{3!2!1!} = \frac{120}{6 \cdot 2} = 10$.

2. Размещения (Порядок важен, выбираем часть)

Используется, когда мы выбираем $k$ элементов из $n$ и расставляем их по порядку (например, распределение мест в гонке).

• Формула: $A_n^k = \frac{n!}{(n-k)!}$
  • Пример: Сколькими способами можно выбрать капитана и его зама из 10 человек? Ответ: $A_{10}^2 = \frac{10!}{8!} = 9 \cdot 10 = 90$.

3. Сочетания (Порядок НЕ важен, выбираем часть)

Используется, когда мы просто формируем группу, команду или набор, и порядок внутри не имеет значения.

• Без повторений: $C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}$
  • Пример: Сколькими способами можно выбрать 3 дежурных из 20 студентов? Ответ: $C_{20}^3 = \frac{20 \cdot 19 \cdot 18}{3 \cdot 2 \cdot 1} = 1140$.
• С повторениями: Если элементы одного типа могут выбираться многократно (например, выбор булочек разных видов).
  • Формула: $\bar{C}n^k = C{n+k-1}^k = \binom{n+k-1}{k}$

Правила сокращенного умножения и упрощения вычислений

В контексте комбинаторики и алгебры «сокращенное умножение» чаще всего относится к технике упрощения дробей с факториалами и большими произведениями перед выполнением арифметических действий. Это позволяет избежать ошибок и считать устно.

Алгоритм быстрого счета

1. Распишите факториалы частично. Не нужно писать $10!$ полностью. Раскройте больший факториал в числителе до значения знаменателя. $$ \frac{10!}{8!} = \frac{10 \cdot 9 \cdot 8!}{8!} $$
2. Сократите общие множители. Уберите одинаковые части в числителе и знаменателе.
3. Разложите числа на множители. Если прямое сокращение невозможно, разложите числа на простые множители. $$ \frac{36 \cdot 25}{9 \cdot 5} = \frac{(4 \cdot 9) \cdot (5 \cdot 5)}{9 \cdot 5} = 4 \cdot 5 = 20 $$

Сводная таблица формул

Практические примеры решения задач

Задача 1: Комбинаторика

Условие: В классе 25 человек. Нужно выбрать старосту, заместителя и физорга. Сколькими способами это можно сделать? Решение:

1. Выбираем 3 человек из 25.
2. Порядок важен (должности разные): староста ≠ физорг.
3. Используем размещения: $A_{25}^3$.
4. Вычисляем с сокращением: $$ A_{25}^3 = \frac{25!}{(25-3)!} = \frac{25!}{22!} = 25 \cdot 24 \cdot 23 = 13,800 $$

Задача 2: Упрощение выражения

Условие: Упростить выражение $\frac{(n+2)!}{(n)!}$. Решение:

1. Раскрываем числитель до знаменателя: $(n+2)! = (n+2) \cdot (n+1) \cdot n!$.
2. Подставляем в дробь: $\frac{(n+2)(n+1)n!}{n!}$.
3. Сокращаем $n!$: Получаем $(n+2)(n+1)$.
4. Раскрываем скобки (формула сокращенного умножения): $n^2 + 3n + 2$.

Частые ошибки

• Путаница между $A$ и $C$. Самая распространенная ошибка — использовать сочетания там, где важен порядок. Всегда проверяйте, меняется ли суть ситуации при перестановке элементов.
• Ошибка в факториале нуля. Помните, что $0! = 1$. Это критично для формул, где $k=n$ или $k=0$.
• Преждевременное умножение. В задачах с дробями и факториалами никогда не умножайте числа в «лоб». Сначала максимально сократите дробь.
• Неверный учет повторений. Если в задаче есть одинаковые объекты (шары одного цвета, одинаковые буквы), стандартные формулы $P, A, C$ без модификации дадут завышенный ответ. Нужно делить на факториалы количества повторений.

FAQ

В чем разница между размещением и сочетанием? Главное отличие — порядок. В размещении последовательность «А, Б» отличается от «Б, А». В сочетании это одна и та же группа {А, Б}. Математически размещение всегда больше или равно сочетанию при тех же $n$ и $k$.

Как быстро посчитать биномиальный коэффициент $\binom{n}{k}$? Используйте свойство симметрии: $\binom{n}{k} = \binom{n}{n-k}$. Легче считать $\binom{100}{98}$ как $\binom{100}{2}$. Также запоминайте треугольник Паскаля для малых значений $n$.

Что делать, если в задаче есть ограничение «хотя бы один»? Чаще всего проще решить задачу через дополнение: найдите общее количество вариантов и вычтите из них количество вариантов, где нужного элемента нет совсем (случай «ни одного»).