Олимпиадный тренинг

Задача . Свойства4


Задача

Темы:
Какая комбинаторная трактовка существует у одного из свойств биномиальных коэффициентов?
1) Пусть из n-элементного множества надо выбрать k-элементное подмножество. Если мы знаем, сколько способов выбора k-1 элементных подмножеств из множества с n-1 элементами, то достаточно умножить эту величину на n и поделить ее на k. Это и будет ответом задачи.
2) Пусть из n-элементного множества надо выбрать k-элементное подмножество, а затем раскрасить один из его элементов. Тогда количество способов решить эту задачу можно посчитать так: сначала выбрать n способами один из элементов исходного множества, а затем посчитать все сочетания из n-1 по k-1. Ответом будет произведение n на указанное количество сочетаний.
3) Пусть из n-элементного множества надо выбрать k-элементное подмножество, а затем среди не выбранных элементов исходного множества выбрать еще 1 элемент k раз и раскрасить его. Тогда количество способов решить эту задачу можно посчитать так: сначала выбрать n способами один из элементов исходного множества, а затем посчитать все сочетания из n-1 по k-1. Ответом будет произведение n на указанное количество сочетаний.
4) Среди предложенных ответов нет правильных трактовок ни одного из свойств биномиальных коэффициентов.

time 500 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя