Задача
COM-B2-M03-P012 Композиции и перегородки
#12
★★★☆☆ Уровень 3 из 5
Докажите, что число способов представить \(n\) как сумму \(k\) положительных целых слагаемых с учётом порядка равно \(\binom{n-1}{k-1}\).
com_3.md (method inspiration)
Поставьте перегородки в промежутки между \(n\) единицами.
Запишем \(n\) единиц в ряд. Чтобы разбить их на \(k\) непустых групп, нужно выбрать \(k-1\) промежутков из \(n-1\) промежутков между соседними единицами и поставить там перегородки. Размеры групп и будут слагаемыми. Обратно, любая композиция задаёт такие перегородки. Ответ \(\binom{n-1}{k-1}\).
Отличайте композиции от разбиений.