$$(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$$
При $x = y = 1$: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$
При $x = 1, y = -1$: $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$ (при $n > 0$)
Размещения без повторений: $A_n^k = \frac{n!}{(n-k)!}$ - количество способов выбрать $k$ элементов из $n$ с учетом порядка
Размещения с повторениями: $n^k$ - количество способов выбрать $k$ элементов из $n$ с учетом порядка, элементы могут повторяться
Перестановки без повторений: $P_n = n!$ - количество способов переставить $n$ различных элементов
Перестановки с повторениями: $\frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}$ - количество перестановок $n$ элементов, где есть $n_i$ одинаковых элементов $i$-го типа
Сочетания без повторений: $C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}$ - количество способов выбрать $k$ элементов из $n$ без учета порядка
Сочетания с повторениями: $\binom{n+k-1}{k} = \binom{n+k-1}{n-1}$ - количество способов выбрать $k$ элементов из $n$ типов с повторениями, порядок не важен
Определение: Треугольная таблица биномиальных коэффициентов $\binom{n}{k}$, где в $n$-й строке находятся коэффициенты разложения $(1+x)^n$
Свойства:
Определение: Последовательность чисел, где каждое число равно сумме двух предыдущих:
$$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \text{ при } n \geq 2$$Первые числа Фибоначчи:
$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots$
Формула Бине:
$$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$$ где $\phi = \frac{1+\sqrt{5}}{2}$ (золотое сечение), $\psi = \frac{1-\sqrt{5}}{2}$Свойства:
Теорема: Конечное множество из $n$ элементов имеет ровно $2^n$ подмножеств.
Доказательство 1 (комбинаторное):
Подмножество определяется тем, какие элементы в него входят. Для каждого из $n$ элементов есть 2 варианта: включить в подмножество или не включить.
Общее количество способов: $\underbrace{2 \times 2 \times \ldots \times 2}_{n \text{ раз}} = 2^n$
Доказательство 2 (через биномиальные коэффициенты):
Количество подмножеств размера $k$ равно $\binom{n}{k}$.
Общее количество подмножеств:
$$\sum_{k=0}^{n} \binom{n}{k} = (1+1)^n = 2^n$$Используем принцип включений-исключений: найдем общее количество пятизначных чисел и вычтем количество чисел, состоящих только из нечетных цифр.
Общее количество пятизначных чисел:
Первая цифра: 1-9 (9 вариантов)
Остальные 4 цифры: 0-9 (по 10 вариантов каждая)
Итого: $9 \times 10^4 = 90000$
Количество пятизначных чисел из нечетных цифр:
Нечетные цифры: 1, 3, 5, 7, 9 (всего 5)
Все 5 позиций могут быть заполнены любой из 5 нечетных цифр
Итого: $5^5 = 3125$
Ответ:
Количество пятизначных чисел с хотя бы одной четной цифрой:
$$90000 - 3125 = 86875$$Интерпретация: Составляем пары "парень-девушка".
Решение:
У нас есть $n$ парней и $n$ девушек. Нужно составить $n$ разнополых пар.
Первого парня можно соединить с любой из $n$ девушек - $n$ способов
Второго парня можно соединить с любой из оставшихся $(n-1)$ девушек - $(n-1)$ способов
И так далее...
Ответ:
$$n \times (n-1) \times (n-2) \times \ldots \times 1 = n!$$Хоровод - это циклическая перестановка, где важен только порядок относительно друг друга, а не абсолютная позиция.
Рассуждение:
Если бы люди стояли в ряд, было бы $n!$ перестановок.
Но в хороводе нет выделенного "начала" - любой поворот дает тот же хоровод.
Каждый хоровод можно получить $n$ способами (поворотами), поэтому:
Ответ:
$$\frac{n!}{n} = (n-1)!$$$$C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}$$
где $n \geq k \geq 0$
Вывод формулы:
Сочетания - это размещения без учета порядка.
Количество размещений из $n$ по $k$: $A_n^k = \frac{n!}{(n-k)!}$
Каждое сочетание можно переставить $k!$ способами
Поэтому: $C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}$
Важные свойства:
$$(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$$
Доказательство (комбинаторное):
При раскрытии $(x+y)^n = \underbrace{(x+y)(x+y)\ldots(x+y)}_{n}$ каждое слагаемое получается выбором из каждой скобки либо $x$, либо $y$.
Слагаемое $x^{n-k}y^k$ получается, если из $k$ скобок выбрать $y$, а из остальных $(n-k)$ выбрать $x$.
Количество способов выбрать $k$ скобок из $n$: $\binom{n}{k}$
Важные следствия:
Идея: Подсчитаем количество способов выбрать $k$ элементов из множества $\{1, 2, \ldots, n\}$ двумя способами.
Способ 1: Прямой подсчет дает $C_n^k$
Способ 2: Разделим все сочетания на два типа:
Подсчет типа A:
Если в сочетании есть элемент $n$, то нужно выбрать еще $(k-1)$ элементов из множества $\{1, 2, \ldots, n-1\}$
Количество способов: $C_{n-1}^{k-1}$
Подсчет типа B:
Если в сочетании нет элемента $n$, то нужно выбрать $k$ элементов из множества $\{1, 2, \ldots, n-1\}$
Количество способов: $C_{n-1}^{k}$
Вывод:
Поскольку каждое $k$-сочетание относится ровно к одному из типов:
$$C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k}$$Шахматная доска имеет размер $8 \times 8$. Фишка должна пройти от $(1,1)$ до $(8,8)$.
Анализ пути:
Чтобы попасть из $(1,1)$ в $(8,8)$, фишка должна:
Всего ходов: $7 + 7 = 14$
Комбинаторная задача:
Нужно выбрать 7 позиций из 14 для ходов вправо (или для ходов вверх).
Ответ:
$$\binom{14}{7} = \frac{14!}{7! \cdot 7!} = 3432$$Если есть $n$ объектов, среди которых $n_1$ объектов первого типа, $n_2$ - второго, ..., $n_k$ - k-го типа, то количество различных перестановок:
$$\frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}$$
где $n = n_1 + n_2 + \ldots + n_k$
Вывод формулы:
Если бы все объекты были различны, было бы $n!$ перестановок.
Но объекты одного типа неразличимы:
Поэтому нужно разделить на произведение факториалов:
$$\frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}$$Количество способов выбрать $k$ объектов из $n$ типов с возможными повторениями:
$$\binom{n+k-1}{k} = \binom{n+k-1}{n-1}$$
Интерпретация: Это количество неотрицательных целых решений уравнения:
$$x_1 + x_2 + \ldots + x_n = k$$Доказательство (метод "звездочек и палочек"):
Представим $k$ одинаковых объектов как звездочки: $\underbrace{* * * \ldots *}_{k}$
Чтобы разделить их на $n$ групп, нужно поставить $(n-1)$ разделитель (палочку)
Всего позиций: $k + (n-1) = n + k - 1$
Нужно выбрать $k$ позиций для звездочек: $\binom{n+k-1}{k}$
Или выбрать $(n-1)$ позиций для палочек: $\binom{n+k-1}{n-1}$
Теорема: $\sum_{k=0}^{n} \left(\binom{n}{k}\right)^2 = \binom{2n}{n}$
Доказательство 1 (комбинаторное):
Рассмотрим задачу: сколько способов выбрать $n$ человек из группы, состоящей из $n$ мужчин и $n$ женщин?
Способ 1: Прямой подсчет дает $\binom{2n}{n}$
Способ 2: Разбиваем по количеству выбранных мужчин:
Доказательство 2 (через производящие функции):
Рассмотрим $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$
Умножим на $(1+x)^n = \sum_{j=0}^{n} \binom{n}{j} x^j$:
$$(1+x)^{2n} = \left(\sum_{k=0}^{n} \binom{n}{k} x^k\right) \left(\sum_{j=0}^{n} \binom{n}{j} x^j\right)$$Коэффициент при $x^n$ слева: $\binom{2n}{n}$
Коэффициент при $x^n$ справа: $\sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k} = \sum_{k=0}^{n} \binom{n}{k}^2$
Ответ: $\sum_{k=0}^{n} \left(\binom{n}{k}\right)^2 = \binom{2n}{n}$
Нужно найти количество способов выбрать 3 элемента из 7 без учета порядка.
Используем формулу сочетаний:
$$\binom{7}{3} = \frac{7!}{3!(7-3)!} = \frac{7!}{3! \cdot 4!}$$Условие: Всего шаров: 5 белых + 3 чёрных = 8 шаров
Вынимаем 4 шара, из них ровно 2 белых (значит, 2 чёрных)
Решение:
Нужно выбрать:
По принципу произведения общее количество способов:
$$\binom{5}{2} \cdot \binom{3}{2}$$Условие:
Метод от противного:
Всего способов - способы без вратарей
Вычисления:
Последовательность определяется рекуррентно:
Первые числа Фибоначчи:
Важные свойства:
Множество из $n$ элементов имеет ровно $2^n$ подмножеств (включая пустое множество и само множество).
Доказательство 1 (комбинаторное):
Для каждого элемента множества есть два выбора: включить его в подмножество или не включать.
Поскольку выборы независимы, общее количество способов: $\underbrace{2 \times 2 \times \ldots \times 2}_{n} = 2^n$.
Доказательство 2 (через биномиальные коэффициенты):
Подмножества можно классифицировать по размеру:
Общее количество:
$$\sum_{k=0}^{n} \binom{n}{k} = (1+1)^n = 2^n$$Доказательство 3 (математическая индукция):
Метод от противного:
Найдем количество пятизначных чисел, в которых все цифры нечетные, и вычтем из общего количества.
Общее количество пятизначных чисел:
От 10000 до 99999, всего: $99999 - 10000 + 1 = 90000$
Количество пятизначных чисел из одних нечетных цифр:
Нечетные цифры: 1, 3, 5, 7, 9 (всего 5 цифр)
Всего чисел из нечетных цифр: $5^5 = 3125$
Количество чисел с хотя бы одной четной цифрой:
$$90000 - 3125 = 86875$$Интерпретация задачи:
Нужно разбить $2n$ человек ($n$ парней и $n$ девушек) на $n$ пар. Предполагаем, что пары могут быть любыми (не обязательно разнополыми).
Решение:
Это классическая задача о количестве способов разбить $2n$ различных объектов на $n$ неупорядоченных пар.
Вывод формулы:
Получаем произведение:
$$(2n-1) \times (2n-3) \times (2n-5) \times \ldots \times 3 \times 1$$Это произведение всех нечетных чисел от 1 до $(2n-1)$, которое равно:
$$\frac{(2n)!}{2^n \cdot n!}$$Альтернативная формула:
$$\frac{(2n)!}{2^n \cdot n!} = (2n-1)!! = 1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n-1)$$Анализ задачи:
Хоровод - это круговое расположение людей, где важен только относительный порядок, а не абсолютные позиции.
Отличия от линейных перестановок:
Случай 1: Различаем направление (по часовой/против часовой стрелки)
Зафиксируем одного человека в определенной позиции (чтобы исключить повороты).
Остальных $(n-1)$ человек можно расставить $(n-1)!$ способами.
Случай 2: Не различаем направление (отражения считаются одинаковыми)
Каждая конфигурация и ее отражение считаются одинаковыми.
Количество способов: $\frac{(n-1)!}{2}$ при $n \geq 3$.