Задача
COM-B2-M09-P015 Выбор без соседей
#15
★★★★☆ Уровень 4 из 5
Докажите, что число способов выбрать \(k\) чисел из \(\{1,2,\ldots,n\}\) так, чтобы никакие два выбранных числа не были соседними, равно \(\binom{n-k+1}{k}\).
Если выбранные числа \(i_1<\cdots
Пусть выбраны \(i_1<\cdots
Хотя решение биективное, оно объясняет коэффициент в полиноме независимых подмножеств пути.