C++
Mathematics
Comments 12
+8

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

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

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

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

Книжка для чтения — Липский "комбинаторика для программиста".
Буду не сонный — проверю вашу формулу для вычисления, обычно считают как n·...·(n-l+1)/(1·...·l), выводится очень просто: первый элемент можем выбрать n способами, второй n-1 и так далее — получаем "число размещений", т.е. сколькими способами можно выбрать упорядоченную последовательность из l элементов; но порядок нам не важен — делим на l! (число перестановок l элементов, 1·2·...·l).

0

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

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

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

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

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


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

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