Разбиением числа N, как известно, является представление N в виде суммы положительных целых чисел. Например, для N = 4 получаем набор:

  1. 1+1+1+1
  2. 1+1+2
  3. 1+3
  4. 2+2
  5. 4

Если речь идет о композиции числа N, то здесь имеет роль порядок слагаемых. Для того же N получаем набор:

  1. 1+1+1+1
  2. 1+1+2
  3. 1+2+1
  4. 1+3
  5. 2+1+1
  6. 2+2
  7. 3+1
  8. 4

Общее количество композиций для N равно $%2^{N-1}$%. А как быть если слагаемые должны лежать в интервале [1,K]? Здесь приводится формула $%R(N,K)$%, но она зацикливается. Полагаю, что в ней допущена опечатка. В общем случае получаем:

  • $%R(K,K) = 2^{K-1}$%
  • $%R(K+1,K) = 2^K - 1$%
  • $%R(K+2,K) = 2^{K+1} - 3$%
  • $%R(K+3,K) = 2^{K+2} - 8$%
  • $%R(K+4,K) = 2^{K+3} - 20$%
  • $%R(K+5,K) = 2^{K+4} - 48 $%
  • $%R(K+6,K) = 2^{K+5} - 112$%
  • ....

Представленные вычеты {3,8,20,48,112,...} образуют такую последовательность, но когда каждый раз, когда N становится кратным K происходит смещение. Вывести формулу пока не получилось.

Поэтому буду благодарен, если Вы поделитесь корректным вариантом формулы R(N,K) или литературой, где можно об этом почитать.

задан 2 Май '12 16:36

изменен 3 Май '12 15:12

Angry%20Bird's gravatar image


9125

1

У меня когда-то была книга Харари и Палмера "Перечисление графов", там подсчитывается количество всего, что только можно, вплоть до очень сложных рекуррентных и асимптотических формул.
Там еще эпиграфы ко всему (включая список литературы). Может, найдете, но книга старая...

(3 Май '12 12:41) DocentI

"... Общее число композиций для N равно ... А как быть если слагаемые должны лежать в интервале [1, K]?" ipolit

Я не понимаю вопроса "А как быть если слагаемые должны лежать в интервале [1, K]?".

(3 Май '12 14:45) Галактион
1

Для Галактиона: т.е. чему равно число композиций, если все слагаемые лежат в диапазоне $%1 \le a_i \le K \lt N$%

(3 Май '12 15:56) Андрей Юрьевич

Если $%N$% достаточно невелико, то количество композиций можно подсчитать с помощью функции $%R(N,K)$%. Иначе задачу можно решить нахождением N-ого числа Фибоначчи через быстрое возведение в степень исходной матрицы. Данный подход описан в книге А.Шень "Программирование. Теоремы и задачи". Для n-step чисел Фибоначчи нужно подобрать соответствующую матрицу.

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

В любом случае, спасибо всем, кто откликнулся.

(4 Май '12 11:08) ipolit
10|600 символов нужно символов осталось
2

В общем разобрался с этой проблемой. Для начала приведу корректную формулу $%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

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×967
×17

задан
2 Май '12 16:36

показан
5334 раза

обновлен
4 Май '12 11:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru