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

Главное по теме

• Главный вопрос любой задачи на выбор: важен ли порядок? Поменяй двух выбранных местами. Результат изменился (роли разные) это размещение A. Не изменился (просто группа) это сочетание C.
• Сочетания: выбрать группу из k человек из n без ролей. C(n, k) = n! / (k! · (n − k)!). Два дежурных из 6: C из 6 по 2 = 6 · 5 / 2 = 15.
• Размещения: выбрать k человек на k разных ролей из n. A(n, k) = n! / (n − k)! = n · (n − 1) · ... (k множителей). Староста и зам из 6: 6 · 5 = 30.
• Быстрый счёт C: в числителе k множителей сверху, начиная с n и убывая, в знаменателе k!. C из 8 по 3 = 8 · 7 · 63 · 2 · 1 = 56.
• Связь формул: A(n, k) = C(n, k) · k!. Размещений всегда больше в k! раз, потому что каждую группу ещё расставляют по ролям.
• Делегация из нескольких групп: выбираем из каждой группы отдельно и перемножаем. 2 юноши из 6 И 2 девушки из 4: C из 6 по 2 · C из 4 по 2 = 15 · 6 = 90.
• Условие «не менее», «хотя бы», «не более»: разбей на случаи (ровно 2, ровно 3, ...), посчитай каждый, сложи. Или считай через дополнение: всё минус запрещённое.
• Рукопожатия, матчи «каждый с каждым», отрезки между точками, визитки парами: это пары без порядка, C(n, 2) = n · n − 12. Восемь человек: 28 рукопожатий.
• Капитан и вратарь из 11 это A(11, 2) = 110, а двое в сборную без ролей это C(11, 2) = 55. Разные роли удваивают счёт.
• Полезные значения: C(5, 2) = 10, C(6, 2) = 15, C(7, 2) = 21, C(8, 2) = 28, C(6, 3) = 20, C(7, 3) = 35, C(8, 3) = 56. C(n, k) = C(n, n − k): выбрать 3 из 8 это то же, что отбросить 5.

Задания с разбором

Объяснение простыми словами

В классе выбирают двух дежурных. Айдар и Дана, или Дана и Айдар, это одна и та же пара, никто не главный, оба моют доску. А теперь выбирают старосту и его заместителя. Айдар староста и Дана зам, или Дана староста и Айдар зам, это уже два разных варианта. Задачи выглядят одинаково, в обоих выбирают двоих из класса, но ответы отличаются вдвое. Вся сегодняшняя тема держится на одном вопросе: важен ли порядок выбора?

Проверить это просто. Выбери двух человек и мысленно поменяй их местами. Если результат изменился, потому что у них разные роли, разные места или разные призы, то порядок важен. Если ничего не изменилось, потому что это просто группа, то порядок не важен. Группу без ролей считают сочетаниями и пишут C(n, k), читается «C из n по k». Выбор на разные роли считают размещениями и пишут A(n, k). Слова, которые выдают размещение: капитан и вратарь, председатель и секретарь, первое, второе и третье место, золото, серебро, бронза. Слова, которые выдают сочетание: команда, делегация, комиссия, букет, набор, дежурные.

Дальше в Biik: продолжение объяснения, видеоразбор и проверка из 8 заданий по этой теме.

Термины

Сочетание

Набор из k предметов, выбранных из n, в котором порядок не важен; обозначается C(n, k) или «C из n по k».

Размещение

Выбор k предметов из n с учётом порядка или ролей; обозначается A(n, k).

Порядок важен

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

Порядок не важен

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

Факториал

n! это произведение всех чисел от 1 до n; 4! = 24, 5! = 120.

Роль

Отличительная должность или место: капитан, вратарь, председатель, золотая медаль. Роли делают порядок важным.

Группа без ролей

Команда, комиссия, делегация, где все выбранные равноправны; считается сочетаниями.

Делегация из нескольких групп

Состав, где заданное число человек берут из каждой группы отдельно; результаты по группам перемножают.

Правило умножения

Если выбирают и из одной группы, и из другой, числа способов перемножают.

Правило сложения

Если возможны разные несовместимые случаи, число способов по каждому случаю складывают.

Разбор случаев

Способ решить «не менее» или «хотя бы»: перечислить допустимые варианты состава и сложить их.

Дополнение

Все варианты минус те, что запрещены; удобно для «хотя бы один» и «не вместе».

Хотя бы один

Один или больше. Считается как всё минус «ни одного».

Не менее двух

Два или больше. Случаи: ровно 2, ровно 3 и так далее до максимума.

Рукопожатие

Пара людей без порядка; число рукопожатий среди n человек равно C(n, 2).

Круговой турнир

Каждая команда играет с каждой один раз; матчей C(n, 2). Если дома и в гостях, то вдвое больше.

Симметрия сочетаний

C(n, k) = C(n, n − k): выбрать k человек это то же, что выбрать n − k, которые останутся.

Треугольник по точкам

Любые 3 точки окружности дают треугольник; их число C(n, 3).