Математика с нуля
Сочетания
Ты приглашаешь 2 друзей из группы в 4 на ужин. Пригласить Аню и Борю — это ровно тот же ужин, что пригласить Борю и Аню — порядок, в котором ты их назвал, ничего не меняет. Когда порядок перестаёт иметь значение, ты считаешь сочетания.
После этого урока ты можешь сказать, что такое сочетание, увидеть, чем оно отличается от перестановки, и считать сочетания, деля перестановки на порядки, которые ты больше не хочешь считать отдельно.
Сочетание — это выбор, где порядок не важен. Перестановка заботилась о месте —
золото, серебро, бронза были все разными. Сочетание заботится лишь о том, кто
выбран, а не в каком порядке. Группа A, B и группа B, A — одно и то же сочетание,
ведь в них одни и те же люди.
Сочетаний меньше, чем перестановок того же выбора. Выбрать 2 из 4 человек
упорядоченным списком — перестановка — даёт 4 × 3 = 12 результатов. Но A потом B и
B потом A — один и тот же ужин. 12 упорядоченных списков схлопываются в меньшее число
неупорядоченных групп. Счёт сочетаний всегда меньше соответствующего счёта
перестановок.
Считай сочетание, деля перестановки на порядки выбранной группы. Выбор 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!.
Выбери 2 человек из 4, порядок не важен. Напиши число сочетаний.
Выбери 1 человека из 7, порядок не важен. Напиши число сочетаний.
Выбери 3 человек из 5, порядок не важен. Напиши число сочетаний.
Выбор 2 из 5 даёт 20 упорядоченных выборов. Раздели на 2, чтобы получить сочетания. Напиши результат.
Выбери 4 человек из группы в 4, порядок не важен. Напиши число сочетаний.
Почему число сочетаний меньше числа перестановок для того же выбора?
Сочетание — это выбор, где порядок не важен: группа A, B — то же, что B, A.
Сочетаний меньше, чем соответствующих перестановок, ведь перестановки считают каждую
группу по разу на каждый порядок. Чтобы посчитать сочетания, возьми счёт перестановок
и раздели на r!, факториал размера группы — это деление сливает дублирующие порядки
обратно в одиночные группы.