Comments 12
Возможно, вы просто не изучали комбинаторику, но это чуть ли не самая известная формула. Сама конструкция называется сочетаниями из n по k: https://ru.wikipedia.org/wiki/Сочетание. В русских учебниках обычно обозначается как C_n^k. И формула традиционно записывается через факториалы: n!/(k!(n-k)!). По запросу "сумма сумм" такое вряд ли найдётся, но ведь и задача изначально сформулирована вами как выбор k ячеек из n, это и надо было искать.
P.S. в некоторых начальных формулах, где только суммы по i, опечатка, под знаком суммы вообще не участвует i.
Насчет доказательства еще подумаю. Но, как указали выше, это число сочетаний. Так что формула доказана без всякой мат. индукции.
Книжка для чтения — Липский "комбинаторика для программиста".
Буду не сонный — проверю вашу формулу для вычисления, обычно считают как n·...·(n-l+1)/(1·...·l), выводится очень просто: первый элемент можем выбрать n способами, второй n-1 и так далее — получаем "число размещений", т.е. сколькими способами можно выбрать упорядоченную последовательность из l элементов; но порядок нам не важен — делим на l! (число перестановок l элементов, 1·2·...·l).
Ну незнаю. Так то формулировка вполне известная: "Задача о шарах и перегородках", А S_l(n) \eq C_n^l, число сочетаний. Другая формулировка: число решений уравнения \sum_{i = 1}^{l+1}{x_i} \eq N-l, x_i \in \mathbb{N}_0, в ней ваше доп условие про r задается так x_i < r (если вычесть из общего числа вариантов). Теперь методом динамического программирования должно получиться простое решение за O(nl*bigint_add) (чтобы получилось без r нужно сумму на отрезке выразить через предыдущее значение) которое выглядит естественнее того что написано в статье. Возможно с мемоизацией ваше решение не так уж и плохо, но точно выглядит ужасно.
Насколько я понял, динамическое программирование — это метод решения рекуррентной зависимости. Если реализовать эту зависимость без рекурсии и с минимальной (но достаточной) мемоизацией, то получится ДП. У меня тут две зависимости (формулы для r > 0), реализованные просто через рекурсивные функции. Это дело техники — реализовать их с помощью ДП. Главная сложность в том, чтобы получить сами зависимости. Или я что-то упускаю?
Я совсем не мастер оценивать сложность, но думаю, для 1-й формулы она будет пропорциональна r(l — 1), а для второй — пропорциональна l(n — 2r — 1). Это с мемоизацией, конечно же.
Как уже сказали выше, Вы с одной стороны большой молодец, что прорешиваете такие задачки и приходите к ним не общеизвестными и самыми популярными способами, а своими методами. Это крайне полезно. С другой стороны, не стоит с этим перегибать. После Ваших упражнений стоит поглядеть, как это делают чаще всего, посколько ассимптотически почти наверное, Вы сделаете это неэффективно.
В частности, цэшки (о которых речь идёт в самом начале) выччисляются очень просто путём деления кратных множетелей. Более того, во многих задачах никакой длинки не нужно.
Сумма сумм арифметических прогрессий