Comments 12

Возможно, вы просто не изучали комбинаторику, но это чуть ли не самая известная формула. Сама конструкция называется сочетаниями из n по k: https://ru.wikipedia.org/wiki/Сочетание. В русских учебниках обычно обозначается как C_n^k. И формула традиционно записывается через факториалы: n!/(k!(n-k)!). По запросу "сумма сумм" такое вряд ли найдётся, но ведь и задача изначально сформулирована вами как выбор k ячеек из n, это и надо было искать.

Это почти самое старое и самое известное в математике, еще даже до комбинаторики. Ферма еще этим увлекался, треугольные числа, тетраэдрические числа и т.п.
Не то чтоб не изучал, а просто забыл ее напрочь. Это и правда число сочетаний.

Чувствую себя идиотом. А Вам спасибо.
Вы все равно молодец, ибо сами проделали этот путь и это намного лучше, чем просто взять готовую формулу и использовать.
Не хочу придираться, но доказательство крайне «нестрогое». Нельзя предполагать в шаге мат. индукции истинность формулы для L, затем вычитать тождества и приводить все к тождеству, поэтому в мат. индукции часто используется вместе с методом искл. 3-го: Предположим формула для L-1 верна, а для L — нет, получаем противоречие. Или надо вести цепочку тождеств от формул, где есть только L-1. Формула, конечно, но надо бы построже.
P.S. в некоторых начальных формулах, где только суммы по i, опечатка, под знаком суммы вообще не участвует i.
Да, там одна формула встречалась в статье 3 раза, и в ней была опечатка. Уже исправил. Спасибо!

Насчет доказательства еще подумаю. Но, как указали выше, это число сочетаний. Так что формула доказана без всякой мат. индукции.
Я думаю, что разобрался с доказательством. Там применяется метод мат. индукции 2 раза: сначала по l, потом по n. Я исправил статью. Формулы остались те же, но добавились пояснения.

Книжка для чтения — Липский "комбинаторика для программиста".
Буду не сонный — проверю вашу формулу для вычисления, обычно считают как 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 нужно сумму на отрезке выразить через предыдущее значение) которое выглядит естественнее того что написано в статье. Возможно с мемоизацией ваше решение не так уж и плохо, но точно выглядит ужасно.

Да, у меня как раз та же задача, что с шарами и перегородками. Ответ на нее — C из N по l. Это тут все заметили, кроме меня. Спасибо.

Насколько я понял, динамическое программирование — это метод решения рекуррентной зависимости. Если реализовать эту зависимость без рекурсии и с минимальной (но достаточной) мемоизацией, то получится ДП. У меня тут две зависимости (формулы для r > 0), реализованные просто через рекурсивные функции. Это дело техники — реализовать их с помощью ДП. Главная сложность в том, чтобы получить сами зависимости. Или я что-то упускаю?

Я совсем не мастер оценивать сложность, но думаю, для 1-й формулы она будет пропорциональна r(l — 1), а для второй — пропорциональна l(n — 2r — 1). Это с мемоизацией, конечно же.

Как уже сказали выше, Вы с одной стороны большой молодец, что прорешиваете такие задачки и приходите к ним не общеизвестными и самыми популярными способами, а своими методами. Это крайне полезно. С другой стороны, не стоит с этим перегибать. После Ваших упражнений стоит поглядеть, как это делают чаще всего, посколько ассимптотически почти наверное, Вы сделаете это неэффективно.


В частности, цэшки (о которых речь идёт в самом начале) выччисляются очень просто путём деления кратных множетелей. Более того, во многих задачах никакой длинки не нужно.

Only those users with full accounts are able to leave comments. Log in, please.