v1 · padrão canônico

Lição 38 — Combinações e binômio de Newton

Combinação C(n,r): selecionar r objetos de n sem importar a ordem. Triângulo de Pascal, identidade de Pascal, teorema do binômio de Newton.

Used in: 1.º ano do EM (15–16 anos) · Equiv. Math I japonês cap. 2 · Equiv. Klasse 10–11 alemã Stochastik

\binom{n}{r} = \frac{n!}{r!\,(n-r)!}

Учебники, охватывающие этот урок

Book of Proof, 3-е изд. — Richard Hammack · §3.1–§3.4 · CC-BY-ND · Основной источник по комбинациям, треугольнику Паскаля и биному с полными доказательствами по индукции.
OpenStax Algebra and Trigonometry 2e — Jay Abramson et al. · §13.5–§13.6 · CC-BY · Прикладные упражнения по подсчету, перестановкам, комбинациям и биномиальной теореме с доступной нотацией.
Discrete Mathematics: An Open Introduction, 3-е изд. — Oscar Levin · §1.2–§1.3 · CC-BY-SA · Современный комбинаторный подход с аргументами двойного подсчета и тождествами без слов.

Choose your door

Rigorous notation, full derivation, hypotheses

Строгое определение

Простая комбинация

Definition· Комбинация из n элементов по r

Пусть $n \in \mathbb{N}$ и $r \in \mathbb{N}$ при $0 \leq r \leq n$ . Комбинация $C(n, r)$ — это подмножество из $r$ элементов, выбранных из набора из $n$ различных элементов. Количество таких подмножеств равно:

\binom{n}{r} = \frac{n!}{r!\,(n-r)!}

what this means · Формула центральной комбинации. Знаменатель r! исключает r! различных порядков, в которых одно и то же подмножество может быть представлено как размещение.

"Комбинация — это выбор объектов из коллекции таким образом, что порядок выбора не имеет значения." — OpenStax Algebra and Trigonometry 2e, §13.5

Связь с перестановками

Definition· Размещение против комбинации

Размещение (частичная перестановка) из $n$ элементов по $r$ :

P(n, r) = \frac{n!}{(n-r)!}

what this means · Размещение подсчитывает упорядоченные последовательности; комбинация подсчитывает неупорядоченные группы.

Каждое подмножество из $r$ элементов может быть упорядочено $r!$ способами, следовательно:

\binom{n}{r} = \frac{P(n,r)}{r!} = \frac{n!}{r!\,(n-r)!}

what this means · Комбинация — это размещение, деленное на количество возможных порядков выбранного подмножества.

Фундаментальные свойства

Definition· Свойства биномиальных коэффициентов

Свойство	Формула
Крайние случаи	$\binom{n}{0} = \binom{n}{n} = 1$
Единичный случай	$\binom{n}{1} = \binom{n}{n-1} = n$
Симметрия	$\binom{n}{r} = \binom{n}{n-r}$
Рекуррентность Паскаля	$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$
Полная сумма	$\displaystyle\sum_{r=0}^{n} \binom{n}{r} = 2^n$
Альтернирующая сумма	$\displaystyle\sum_{r=0}^{n} (-1)^r \binom{n}{r} = 0$ при $n \geq 1$

Треугольник Паскаля

Рекуррентность Паскаля $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ генерирует треугольник. Каждый элемент — сумма двух элементов прямо выше.

Треугольник Паскаля — строки 0 по 6. Строка 4 (выделена) содержит коэффициенты $(a+b)^4$ .

Биномиальная теорема Ньютона

"Биномиальный коэффициент $\binom{n}{r}$ — это количество подмножеств из $r$ элементов набора, содержащего $n$ элементов." — Hammack, Book of Proof 3-е изд., §3.3

"Каждое число в треугольнике Паскаля — это сумма двух чисел прямо над ним." — Levin, Discrete Mathematics: An Open Introduction, §1.2

Решенные примеры

Example· Прямой расчет комбинации

Задача: Учитель хочет выбрать 3 студентов из класса 10, чтобы представить школу на олимпиаде. Сколькими различными способами он может это сделать?

Стратегия: Порядок выбранных студентов не важен — любая группа из 3 студентов одинаково представляет школу. Используем формулу комбинации.

Решение:

Определить $n$ и $r$ : $n = 10$ (всего студентов), $r = 3$ (студентов выбрать).
Применить формулу: $\binom{10}{3} = \frac{10!}{3!\,(10-3)!} = \frac{10!}{3!\cdot 7!}$
Упростить — сократить $7!$ : $= \frac{10 \cdot 9 \cdot 8}{3!} = \frac{720}{6} = 120$

Заключение: Существует 120 различных групп из 3 студентов.

Проверка: $\binom{10}{3} = \binom{10}{7}$ (симметрия) $= \frac{10!}{7!\cdot3!} = 120$ . Согласуется.

Источник. Hammack, Book of Proof 3-е изд., §3.3, ex. 3 — лицензия CC-BY-ND.

Example· Комбинация против перестановки — прямой контраст

Задача: Клуб имеет 8 членов. (a) Сколькими способами можно выбрать директорат из 3 различных должностей (президент, вице и казначей)? (b) Сколькими способами можно выбрать комиссию из 3 членов без различия должностей?

Стратегия: (a) Порядок важен: три должности различны. Используем размещение. (b) Порядок не важен: любая группа из 3 эквивалентна. Используем комбинацию.

Решение:

(a) Директорат (размещение): $P(8, 3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336$

(b) Комиссия (комбинация): $\binom{8}{3} = \frac{8!}{3!\cdot 5!} = \frac{8 \cdot 7 \cdot 6}{6} = 56$

Связь между результатами: $P(8, 3) = 3! \cdot \binom{8}{3}$ , так как $336 = 6 \cdot 56$ . Каждая комиссия из 3 может быть организована 6 различными способами назначения должностей.

Источник. OpenStax Algebra and Trigonometry 2e, §13.5, example 4 — лицензия CC-BY 4.0.

Example· Тождество Паскаля и треугольник

Задача: (a) Проверьте тождество Паскаля для $n = 6$ , $r = 2$ : $\binom{5}{1} + \binom{5}{2} = \binom{6}{2}$ . (b) Постройте строки 0 по 5 треугольника Паскаля и найдите $\binom{5}{2}$ .

Стратегия: (a) Вычислить каждый бином и проверить равенство численно. (b) Применить рекуррентность: каждый элемент — сумма двух выше.

Решение:

(a) Численная проверка: $\binom{5}{1} = 5, \qquad \binom{5}{2} = \frac{5!}{2!\cdot 3!} = 10, \qquad \binom{6}{2} = \frac{6!}{2!\cdot 4!} = 15$

$\binom{5}{1} + \binom{5}{2} = 5 + 10 = 15 = \binom{6}{2} \checkmark$

(b) Треугольник Паскаля (строки 0 по 5):

\begin{array}{ccccccccccc} & & & & & 1 & & & & & \\ & & & & 1 & & 1 & & & & \\ & & & 1 & & 2 & & 1 & & & \\ & & 1 & & 3 & & 3 & & 1 & & \\ & 1 & & 4 & & 6 & & 4 & & 1 & \\ 1 & & 5 & & 10 & & 10 & & 5 & & 1 \end{array}

На строке 5 третий элемент (позиция $r = 2$ ) — это $\binom{5}{2} = 10$ .

Проверка: Тождество Паскаля видно визуально: каждое число — сумма двух выше.

Источник. Hammack, Book of Proof 3-е изд., §3.4 — лицензия CC-BY-ND.

Example· Разложение по биномиальной теореме Ньютона — общий член

Задача: Разложите $(2x - 3)^4$ по теореме Ньютона и найдите коэффициент при $x^2$ .

Стратегия: Определить $a = 2x$ , $b = -3$ , $n = 4$ . Применить $T_{r+1} = \binom{4}{r}(2x)^{4-r}(-3)^r$ . Для члена при $x^2$ показатель $x$ должен быть 2, то есть $4 - r = 2$ , откуда $r = 2$ .

Решение:

$r$	$\binom{4}{r}$	$(2x)^{4-r}$	$(-3)^r$	Член
0	1	$16x^4$	1	$16x^4$
1	4	$8x^3$	$-3$	$-96x^3$
2	6	$4x^2$	$9$	$216x^2$
3	4	$2x$	$-27$	$-216x$
4	1	$1$	$81$	$81$

$(2x - 3)^4 = 16x^4 - 96x^3 + 216x^2 - 216x + 81$

Коэффициент при $x^2$ : $\binom{4}{2}(2)^2(-3)^2 = 6 \cdot 4 \cdot 9 = \mathbf{216}$ .

Проверка (частный случай): Для $x = 1$ : $(2 - 3)^4 = 1$ . Подставляя в разложение: $16 - 96 + 216 - 216 + 81 = 1$ . $\checkmark$

Источник. OpenStax Algebra and Trigonometry 2e, §13.6, example 3 — лицензия CC-BY 4.0.

Example· Вероятность рук из колоды карт

Задача: В колоде из 52 карт (4 масти, 13 карт по масти) вычислите: (a) общее количество рук из 5 карт; (b) количество рук ровно с 2 тузами; (c) вероятность руки ровно с 2 тузами.

Стратегия: Использовать комбинации для подсчета подмножеств. В колоде 4 туза и 48 не-тузов. Для (b): выберите 2 из 4 тузов и 3 из 48 остальных карт.

Решение:

(a) Всего рук: $\binom{52}{5} = \frac{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48}{120} = 2\,598\,960$

(b) Руки с ровно 2 тузами: $\binom{4}{2} \cdot \binom{48}{3} = 6 \cdot 17\,296 = 103\,776$

(c) Вероятность: $P(\text{ровно 2 туза}) = \frac{103\,776}{2\,598\,960} \approx 0{,}0399 \approx 4\%$

Интерпретация: Приблизительно 4 из каждых 100 рук покера будут иметь ровно 2 туза.

Проверка: $\binom{48}{3} = \frac{48 \cdot 47 \cdot 46}{6} = \frac{103\,776}{6} = 17\,296$ . Правильно.

Источник. OpenStax Algebra and Trigonometry 2e, §13.5, example 6 — лицензия CC-BY 4.0.

Exercise list

40 exercises · 10 with worked solution (25%)

Application 26Understanding 3Modeling 9Challenge 1Proof 1

Ex. 38.1Application
Вычислите $\binom{5}{2}$ .
Solve online
Ex. 38.2ApplicationAnswer key
Вычислите $\binom{8}{3}$ .
Solve online
Ex. 38.3Application
Вычислите $\binom{10}{5}$ .
Solve online
Ex. 38.4Application
Какое значение $\binom{n}{0}$ для любого $n \geq 0$ ? Обоснуйте комбинаторно.
Solve online
Ex. 38.5Application
Какое значение $\binom{n}{1}$ для любого $n \geq 1$ ? Обоснуйте комбинаторно.
Solve online
Ex. 38.6ApplicationAnswer key
Вычислите $\binom{20}{18}$ , используя симметрию $\binom{n}{r} = \binom{n}{n-r}$ .
Solve online
Ex. 38.7ApplicationAnswer key
Численно проверьте тождество Паскаля: $\binom{6}{2} + \binom{6}{3} = \binom{7}{3}$ . Вычислите все три бинома.
Solve online
Ex. 38.8Application
Сколькими различными способами можно выбрать комиссию из 4 членов из группы 10 человек?
Solve online
Ex. 38.9Application
Мега-Сена выбирает 6 чисел из 60 доступных. Сколько существует различных простых ставок?
Solve online
Ex. 38.10Application
Сколько групп из 4 можно составить из 15 студентов?
Solve online
Ex. 38.11Application
Сколько различных подмножеств (включая пустое и полный набор) имеет набор $\{a, b, c, d, e\}$ ?
Solve online
Ex. 38.12ApplicationAnswer key
Сколько различных рук из 5 карт можно извлечь из колоды 52 карт?
Solve online
Ex. 38.13Application
Какой коэффициент при $x^3$ в разложении $(1 + x)^5$ по теореме Ньютона?
Solve online
Ex. 38.14Application
Какой коэффициент при $x^4 y^2$ в разложении $(x + y)^6$ ?
Solve online
Ex. 38.15Application
Разложите $(x + 1)^4$ по теореме Ньютона. Напишите все члены.
Solve online
Ex. 38.16Application
Разложите $(2x - 3)^3$ по теореме Ньютона.
Solve online
Ex. 38.17ApplicationAnswer key
Какой средний член (4-й член, $T_4$ ) из $(a + b)^6$ ?
Solve online
Ex. 38.18Application
Какой коэффициент при $x^7$ в разложении $(2x + 3)^{10}$ ?
Solve online
Ex. 38.19Application
Найдите значение $p$ такое, что $\binom{20}{p} = \binom{20}{p-2}$ .
Solve online
Ex. 38.20Application
Какой коэффициент при $x^{10}$ в разложении $(1 + x)^{20}$ ?
Solve online
Ex. 38.21Application
Явно проверьте для $n = 5$ , что $\displaystyle\sum_{r=0}^{5} \binom{5}{r} = 2^5$ . Перечислите все члены.
Solve online
Ex. 38.22Application
Сколько различных треугольников можно составить, соединив 3 вершины правильного восьмиугольника?
Solve online
Ex. 38.23Application
Сколько диагоналей имеет многоугольник с 10 сторонами?
Solve online
Ex. 38.24Application
Вычислите $\binom{9}{3}$ .
Solve online
Ex. 38.25Application
Напишите все значения 7-й строки (индекс 6) треугольника Паскаля.
Solve online
Ex. 38.26ApplicationAnswer key
Какой коэффициент при $x^5$ в разложении $(1 + x)^{10}$ ?
Solve online
Ex. 38.27Understanding
Какое концептуальное различие между комбинацией $\binom{n}{r}$ и размещением $P(n, r)$ ?
Solve online
Ex. 38.28Modeling
Из группы 10 мужчин и 8 женщин, сколько комиссий из 5 человек можно составить ровно с 3 мужчинами и 2 женщинами?
Solve online
Ex. 38.29ModelingAnswer key
Сколько целых неотрицательных решений имеет уравнение $x + y + z = 10$ ?
Solve online
Ex. 38.30Modeling
В колоде 52 карт, сколько рук из 5 карт имеют ровно 2 туза?
Solve online
Ex. 38.31Modeling
Сколько различных путей существует из $(0, 0)$ в $(5, 3)$ , используя только единичные шаги вправо или вверх?
Solve online
Ex. 38.32Modeling
Какова вероятность выиграть Мега-Сену с единственным билетом (6 чисел из 60)?
Solve online
Ex. 38.33ModelingAnswer key
В исследовании рынка аналитику нужно выбрать 5 продуктов для анализа из портфеля 20. Сколькими способами она может сделать этот выбор?
Solve online
Ex. 38.34Modeling
Честная монета подбрасывается 10 раз. Вычислите вероятность получить ровно 5 орлов, используя биномиальное распределение $P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$ .
Solve online
Ex. 38.35Modeling
Сколькими способами можно распределить 8 одинаковых конфет между 3 детьми (каждый ребенок может получить ноль или больше конфет)?
Solve online
Ex. 38.36ModelingAnswer key
В классе 30 учащихся, сколько команд из 5 можно составить?
Solve online
Ex. 38.37Understanding
Почему $\binom{n}{r} = \binom{n}{n-r}$ ? Какова правильная комбинаторная интерпретация?
Solve online
Ex. 38.38Understanding
Какой наиболее элегантный способ доказать, что $\displaystyle\sum_{r=0}^{n} \binom{n}{r} = 2^n$ ?
Solve online
Ex. 38.39ChallengeAnswer key
Какой коэффициент независимого члена от $x$ в разложении $\left(x + \dfrac{1}{x}\right)^{10}$ ?
Solve online
Ex. 38.40Proof
Докажите теорему Ньютона по индукции по $n$ . Явно определите, где тождество Паскаля используется в индукционном шаге.
Solve online

Источники

Book of Proof, 3-е изд. — Richard Hammack · 2018 · EN · CC-BY-ND · §3.1 (Списки и комбинации), §3.3 (Подмножества), §3.4 (Треугольник Паскаля и бином). Первичный источник.
OpenStax Algebra and Trigonometry 2e — Jay Abramson et al. · 2022 · EN · CC-BY 4.0 · §13.5 (Принципы подсчета), §13.6 (Биномиальная теорема).
Discrete Mathematics: An Open Introduction, 3-е изд. — Oscar Levin · 2019 · EN · CC-BY-SA · §1.2–§1.3 (Биномиальные коэффициенты и комбинаторные тождества).