|
Разбиением числа N, как известно, является представление N в виде суммы положительных целых чисел. Например, для N = 4 получаем набор:
Если речь идет о композиции числа N, то здесь имеет роль порядок слагаемых. Для того же N получаем набор:
Общее количество композиций для N равно $%2^{N-1}$%. А как быть если слагаемые должны лежать в интервале [1,K]? Здесь приводится формула $%R(N,K)$%, но она зацикливается. Полагаю, что в ней допущена опечатка. В общем случае получаем:
Представленные вычеты {3,8,20,48,112,...} образуют такую последовательность, но когда каждый раз, когда N становится кратным K происходит смещение. Вывести формулу пока не получилось. Поэтому буду благодарен, если Вы поделитесь корректным вариантом формулы R(N,K) или литературой, где можно об этом почитать. задан 2 Май '12 16:36 
ipolit |
|
В общем разобрался с этой проблемой. Для начала приведу корректную формулу $%R(N,K)=\sum _{ i=1 }^{ K }{ R(N-i,K) }$% . Её можно получить если свести исходную задачу к задаче Зайчик: Если K = 2, то получаем, что функция $%R(N,K)$% генерирует числа Фибоначчи, а для произвольного K получаем так называемые n-step числа Фибоначчи: Трибоначчи (N=3) или Тетраначчи (N=4). отвечен 4 Май '12 11:08
ipolit |
Количество способов разложить число в сумму (композиции).
У меня когда-то была книга Харари и Палмера "Перечисление графов", там подсчитывается количество всего, что только можно, вплоть до очень сложных рекуррентных и асимптотических формул.
Там еще эпиграфы ко всему (включая список литературы). Может, найдете, но книга старая...
"... Общее число композиций для N равно ... А как быть если слагаемые должны лежать в интервале [1, K]?" ipolit
Я не понимаю вопроса "А как быть если слагаемые должны лежать в интервале [1, K]?".
Для Галактиона: т.е. чему равно число композиций, если все слагаемые лежат в диапазоне $%1 \le a_i \le K \lt N$%
Если $%N$% достаточно невелико, то количество композиций можно подсчитать с помощью функции $%R(N,K)$%. Иначе задачу можно решить нахождением N-ого числа Фибоначчи через быстрое возведение в степень исходной матрицы. Данный подход описан в книге А.Шень "Программирование. Теоремы и задачи". Для n-step чисел Фибоначчи нужно подобрать соответствующую матрицу.
Идею с производящей функцией не использовал, т.к. там нужно подсчитывать биномиальные коэффициенты, а как это делать быстро для больших значений мне неизвестно.
В любом случае, спасибо всем, кто откликнулся.