Математика с нуля MTH · 09 · 03

Сочетания

Сочетание — это выбор, где порядок не важен; считай его, беря перестановки и деля на порядки, которые ты больше не хочешь различать.

MTH ◷ 16 min

Ты приглашаешь 2 друзей из группы в 4 на ужин. Пригласить Аню и Борю — это ровно тот же ужин, что пригласить Борю и Аню — порядок, в котором ты их назвал, ничего не меняет. Когда порядок перестаёт иметь значение, ты считаешь сочетания.

Цель

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

Сочетание — это выбор, где порядок не важен. Подумай, как часто реальные решения имеют именно такую форму: выбрать комитет, добавить топпинги в пиццу, собрать команду. Ни в одном из этих случаев не важно, в каком порядке ты называл участников — важно лишь, кто вошёл в группу. Перестановка заботилась о месте — золото, серебро, бронза были все разными. Сочетание заботится лишь о том, кто выбран, а не в каком порядке. Группа A, B и группа B, A — одно и то же сочетание, ведь в них одни и те же люди.

Сочетаний меньше, чем перестановок того же выбора. Выбрать 2 из 4 человек упорядоченным списком — перестановка — даёт 4 × 3 = 12 результатов. Но A потом B и B потом A — один и тот же ужин. 12 упорядоченных списков схлопываются в меньшее число неупорядоченных групп. Счёт сочетаний всегда меньше соответствующего счёта перестановок.

6 способов выбрать 2 человек из группы в 4

Считай сочетание, деля перестановки на порядки выбранной группы. Выбор 2 из 4: есть 4 × 3 = 12 упорядоченных выборов. Каждая неупорядоченная пара была посчитана по разу на каждый способ упорядочить 2 человек — а 2 человек можно упорядочить 2! = 2 способами. Значит дели: 12 ÷ 2 = 6 сочетаний.

Правило: перестановки, делённые на факториал размера группы. Чтобы выбрать r предметов из n, когда порядок не важен, сначала посчитай упорядоченные выборы (первые r убывающих множителей n), затем раздели на r! — число порядков r выбранных предметов. Деление убирает ровно те порядки, которые ты решил не различать.

Разбор примера

Сколькими способами можно выбрать 3 человек из группы в 5, когда порядок не важен?

Сначала посчитай упорядоченные выборы — перестановку 3 из 5. Три места, три убывающих множителя: 5 × 4 × 3 = 60.

Но порядок не должен иметь значения. Каждая выбранная группа из 3 была посчитана по разу на каждый порядок этих 3 человек, а 3 человек можно упорядочить 3! = 6 способами.

Вычти эти порядки делением: 60 ÷ 6 = 10. Есть 10 сочетаний. Проверь форму: 10 куда меньше 60 упорядоченных выборов — ровно потому, что каждая группа была посчитана 6 раз.

▸Почему это работает

Почему делить на r!, а не на другое число? Потому что r! — это ровно сколько раз каждая неупорядоченная группа была посчитана. Счёт перестановок перечисляет каждый порядок каждой группы; одна фиксированная группа из r человек появляется во всех r! своих порядках. Деление на r! сливает эти дубликаты обратно в одну группу, которой они всегда и были.

▸Частая ошибка

Частая ошибка — использовать счёт перестановок, когда порядок не важен, говоря, что 2 из 4 человек можно выбрать «12 способами». Это считает A, B и B, A разными, но для ужина они одинаковы. Всякий раз, когда порядок выбранных предметов неважен, дели счёт перестановок на r!.

Практика 0 / 5

Выбери 2 человек из 4, порядок не важен. Напиши число сочетаний.

Выбери 1 человека из 7, порядок не важен. Напиши число сочетаний.

Выбери 3 человек из 5, порядок не важен. Напиши число сочетаний.

Выбор 2 из 5 даёт 20 упорядоченных выборов. Раздели на 2, чтобы получить сочетания. Напиши результат.

Выбери 4 человек из группы в 4, порядок не важен. Напиши число сочетаний.

Проверь себя

Викторина

Почему число сочетаний меньше числа перестановок для того же выбора?

Итог

Сочетание — это выбор, где порядок не важен: группа A, B — то же, что B, A. Сочетаний меньше, чем соответствующих перестановок, ведь перестановки считают каждую группу по разу на каждый порядок. Чтобы посчитать сочетания, возьми счёт перестановок и раздели на r!, факториал размера группы — это деление сливает дублирующие порядки обратно в одиночные группы. Теперь, когда встретишь задачу на выбор, спроси себя: даст ли перестановка двух выбранных элементов другой результат? Если да — перестановка; если нет — раздели на r! и получишь число сочетаний.

Практика

Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.

вспомнитьприменитьуглубить0 из 5 завершено

Что-то непонятно?

Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.