Числа сочетаний (цэ изэн пока)
Ошибка.
Попробуйте повторить позже
В комплекте для сборки игрушечного поезда есть один локомотив (который всегда расположен спереди), 
одинаковых красных вагонов и
одинаковых желтых вагонов. Назовем поезд длинным, если в нем есть хотя бы 
вагонов (не считая локомотива). Сколько различных
длинных поездов можно собрать, используя этот комплект? (Ответ должен быть дан в замкнутом виде: в ответе не должно быть сумм с
переменным числом слагаемых, многоточий и т.д.)
Источники:
Подсказка 1
Сначала хотим найти количество всевозможных поездов, которые можем собрать. Так как длины поездов могут быть различны, удобно рассматривать каждую отдельно. Также, так как количество красных и жёлтых вагонов различно, хотим не рассматривать отдельные случаи (для больших длин, например, когда есть верхняя граница для красных вагонов). В этом случае удобно для каждой длины зафиксировать количество вагонов какого-то одного цвета, а потом выбрать другой цвет. Как это можно обобщить на сумму всех случаев?
Подсказка 2
В общем виде, для длины x, и, допустим, количества красных вагонов y, получаем, что количество поездов будет равно C из x по y (так как вагоны считаются одинаковыми, и нас интересует только расположение цветов). Теперь зафиксируем количество красных вагонов и просуммируем по всевозможным длинам поезда. Получаем какую-то неприятную сумму "цешек", которую, однако, можно упростить, если применить тождество Паскаля. Как нам это помогло?
Подсказка 3
Получаем телескопичесекю сумму, где остается только один биномиальный коэффициент. А теперь вспомним, что нам необходимо просуммировать эти результаты для всевозможного количества красных вагонов. Снова сводим к телескопической сумме. Что дальше?
Подсказка 4
Теперь остается только посчитать количество поездов, в которых менее n вагонов, чтобы вычесть его из общего количества поездов. Здесь задача проще: каждого цвета по количеству вагонов хватает для того, чтобы заполнить поезд любой длины, так что можно не так утруждаться. Как легко посчитать?
Подсказка 5
Можем просто считать, что для каждой позиции имеем 2 варианта: красный или жёлтый. Суммируем по всевозможным длинам (от 0 до n не включительно), вычитаем из ранее найденного и получаем ответ.
Посчитаем количество всех поездов, которые можно собрать в данном наборе, и потом вычтем количество поездов, в которых не более
вагонов.
Зафиксируем число 
и посчитаем, сколько всего поездов с ровно 
красными вагонами. Жёлтых вагонов может быть от
до 
и для каждого числа 
жёлтых вагонов от 
до 
мы выбираем 
мест в строке длины 
Таким образом, искомое
количество поездов с 
красными вагонами равно сумме
Докажем, что эта сумма равна 
Распишем каждое слагаемое, пользуясь следующим тождеством Паскаля:
Мы получим:
В каждой скобке вычитаемое равно уменьшаемому из предыдущей скобки. Нетронутым останется лишь уменьшаемое в последней скобке,
равное 
— это и есть искомый результат сложения.
Заметим, что в силу симметрии биномиальных коэффициентов этот результат можно переписать как
Теперь нужно сложить эти числа по всем 
от 
до 
Получим сумму
которая суммируется аналогичным образом через тождество Паскаля, и результат этого суммирования равен
Мы посчитали количество всех поездов. Осталось лишь вычесть количество поездов, в которых не более 
вагонов, но для каждого
количество поездов длины 
очевидно равно 
а всего в сумме таких поездов 
Таким образом, длинных поездов
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
