bulgakov

13. Сочетания: сколько способов выбрать r из n

Сочетание (без повторений) — это выбор rr разных элементов из nn без учёта порядка. Каждое такое сочетание можно упорядочить r!r! способами и получить r!r! разных размещений. Поэтому число сочетаний равно числу размещений, делённому на r!r!: (nr)=n!r! (n−r)!\dbinom nr=\dfrac{n!}{r!\,(n-r)!}.

Что пригодится из прошлого: размещения — число упорядоченных выборок [n]r[n]_r; перестановки и факториал — сколько способов упорядочить rr элементов и как сокращать дроби с факториалами. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Выбрать двоих или выбрать двоих «с должностями»

Из четырёх человек a,b,c,da,b,c,d нужно выбрать двоих. Есть две разные задачи:

  • староста и заместитель — порядок важен, это размещения: [4]2=4⋅3=12[4]_2=4\cdot3=12 способов;
  • двое дежурных — порядок не важен, это сочетания. Сколько их?

Выпишем все двенадцать размещений и посмотрим, как они группируются:

  • {a, b} → ab, ba — размещений: 2
  • {a, c} → ac, ca — размещений: 2
  • {a, d} → ad, da — размещений: 2
  • {b, c} → bc, cb — размещений: 2
  • {b, d} → bd, db — размещений: 2
  • {c, d} → cd, dc — размещений: 2

Каждая пара людей породила ровно два размещения (кто староста, кто заместитель). Групп столько, сколько способов выбрать двоих; в каждой группе 2!=22!=2 размещения. Поэтому

(42)⋅2!=[4]2=12,(42)=122=6.\binom42\cdot2!=[4]_2=12,\qquad \binom42=\frac{12}{2}=6.

То же для троих из четырёх:

  • {a, b, c} → abc, acb, bac, bca, cab, cba — размещений: 6
  • {a, b, d} → abd, adb, bad, bda, dab, dba — размещений: 6
  • {a, c, d} → acd, adc, cad, cda, dac, dca — размещений: 6
  • {b, c, d} → bcd, bdc, cbd, cdb, dbc, dcb — размещений: 6

Четыре группы по 3!=63!=6 размещений: (43)⋅3!=24=[4]3\binom43\cdot3!=24=[4]_3, поэтому (43)=4\binom43=4.

Формула

Теорема. Число сочетаний без повторений из nn элементов по rr равно

(nr)=n!r! (n−r)!.\boxed{\binom nr=\frac{n!}{r!\,(n-r)!}}.

Доказательство. Рассмотрим все сочетания без повторений из nn элементов по rr и упорядочим каждое из них всеми возможными способами. Получаются размещения без повторений. Проверим, что мы ничего не потеряли и не посчитали дважды:

  • каждое сочетание даёт r!r! различных размещений (все перестановки его rr элементов);
  • разные сочетания дают разные размещения: по размещению однозначно восстанавливается набор его элементов;
  • каждое размещение получено ровно из одного сочетания: достаточно «забыть порядок».

Значит, размещения без повторений разбились на группы по r!r! штук, и групп столько, сколько существует сочетаний:

(nr)⋅r!=[n]r=n(n−1)(n−2)⋯(n−r+1).\binom nr\cdot r!=[n]_r=n(n-1)(n-2)\cdots(n-r+1).

Разделим на r!r! и вспомним, что [n]r=n!(n−r)![n]_r=\dfrac{n!}{(n-r)!} (глава про перестановки):

(nr)=n(n−1)⋯(n−r+1)r!=n!r! (n−r)!.□\binom nr=\frac{n(n-1)\cdots(n-r+1)}{r!}=\frac{n!}{r!\,(n-r)!}.\qquad\square

Как читать запись. (nr)\dbinom nr читается «число сочетаний из nn по rr» или «CC из nn по rr». Её же записывают CnrC_n^r. Верхнее число nn — сколько элементов в запасе, нижнее rr — сколько выбираем. Это не дробь n/rn/r.

Как считать на практике

Большие факториалы считать не нужно. В числителе напишите rr множителей, начиная с nn и уменьшая на единицу, в знаменателе — r!r!, и сокращайте.

(103)=10⋅9⋅83⋅2⋅1=7206=120,(1002)=100⋅992=4950.\binom{10}{3}=\frac{10\cdot9\cdot8}{3\cdot2\cdot1}=\frac{720}{6}=120, \qquad \binom{100}{2}=\frac{100\cdot99}{2}=4950.

Для большого числа элементов получаются знакомые цифры:

  • лотерея «6 из 49»: (496)=13 983 816\dbinom{49}{6}=13\,983\,816;
  • набор из пяти карт из колоды в 52 карты: (525)=2 598 960\dbinom{52}{5}=2\,598\,960.

Особые значения

  • (n0)=1\dbinom n0=1: выбрать ничего можно одним способом (взять пустой набор).
  • (n1)=n\dbinom n1=n: выбрать один элемент можно nn способами.
  • (nn)=1\dbinom nn=1: выбрать всё можно одним способом.
  • (nr)=0\dbinom nr=0 при r>nr>n: нельзя выбрать 55 различных элементов из 33, поэтому способов нет.

Сочетание или размещение?

Комиссия из трёх человек из десяти: порядок не важен, (103)=120\dbinom{10}3=120. Председатель, заместитель и секретарь из тех же десяти: должности разные, порядок важен, [10]3=720[10]_3=720. Видим связь: 720=120⋅3!720=120\cdot3!. Каждой комиссии отвечают 66 способов раздать должности.

Когда «выбираем» связывается с «и»

Задача. В классе 2020 мальчиков и 1515 девочек. Сколькими способами можно выбрать делегацию из двух мальчиков и двух девочек?

Выбор мальчиков и выбор девочек — два шага подряд; число способов каждого шага не зависит от результата другого. По правилу произведения

(202)⋅(152)=190⋅105=19950.\binom{20}{2}\cdot\binom{15}{2}=190\cdot105=19950.

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

  • Делить на r!r! дважды или забыть поделить. Размещения — без деления, сочетания — с делением на r!r!, и один раз.
  • Принимать (nr)\dbinom nr за дробь nr\dfrac nr. (nr)\dbinom nr — число способов, например (42)=6\dbinom42=6, а не 22.
  • Применять формулу, когда порядок важен. Если в задаче есть должности, места, номера — это размещение.
  • Забыть r>nr>n. Тогда сочетаний без повторений нет.

Проверь себя

1. Вычислите (83)\dbinom83.

Решение

(83)=8⋅7⋅63⋅2⋅1=3366=56\dbinom83=\dfrac{8\cdot7\cdot6}{3\cdot2\cdot1}=\dfrac{336}{6}=56.

2. Из двенадцати игроков нужно выбрать стартовую пятёрку. Сколько способов?

Решение

Порядок не важен: (125)=12⋅11⋅10⋅9⋅85!=95040120=792\dbinom{12}5=\dfrac{12\cdot11\cdot10\cdot9\cdot8}{5!}=\dfrac{95040}{120}=792.

3. Из семи человек нужно выбрать комиссию из трёх человек и затем одного из них назначить председателем. Сколько способов?

Решение

Первый путь. Сначала комиссия: (73)=35\dbinom73=35 способов. Затем председатель среди выбранных: 33 способа. Всего 35⋅3=10535\cdot3=105.

Второй путь. Сначала председатель: 77 способов. Затем два остальных члена из оставшихся шести: (62)=15\dbinom62=15. Всего 7⋅15=1057\cdot15=105. Ответы совпали — хорошая проверка.

4. В лотерее «6 из 49» нужно угадать шесть чисел. Сколько существует различных вариантов выбора шести чисел из 4949?

Решение

Порядок не важен: (496)=49⋅48⋅47⋅46⋅45⋅446!=13 983 816\dbinom{49}{6}=\dfrac{49\cdot48\cdot47\cdot46\cdot45\cdot44}{6!}=13\,983\,816.

Итог

  • Сочетание — выбор rr элементов из nn без учёта порядка.
  • Каждое сочетание без повторений порождает r!r! размещений, поэтому (nr)=[n]rr!=n!r! (n−r)!\dbinom nr=\dfrac{[n]_r}{r!}=\dfrac{n!}{r!\,(n-r)!}.
  • Считайте сокращением: rr множителей сверху, r!r! снизу.
  • (n0)=(nn)=1\dbinom n0=\dbinom nn=1, (n1)=n\dbinom n1=n, (nr)=0\dbinom nr=0 при r>nr>n.
ПрактикаЗагружаем тест…