Алгоритм нахождения кол-ва способов разложения натурального числа на сумму

Question

Нужно составить алгоритм нахождения количества способов разложения натурального числа на сумму натуральных чисел (не менее 2).

Этот алгоритм должен представлять из себя некую функцию, которая будет принимать на вход натуральное число (от 2 и выше) и выдавать число способов разложения этого числа на сумму натуральных (не меньше 2).

Например, для числа 6 это будет 4 способа:

6 = 6 = 2 + 4 = 3 + 3 = 2 + 2 + 2

Мне не нужно привязываться к конкретному языку программирования, важен только алгоритм.

Разложение на сумму можно представить в виде графа, например:

На графе 6 вершин, каждая вершина может присоединить к себе 2 других (но минимум 1), но замыкать цепи нельзя:

Таким образом, функция будет принимать такие значения:

f(1) = 0,

f(2) = 1,

f(3) = 1,

f(4) = 2,

f(5) = 2,

f(6) = 4,

f(7) = 4,

f(8) = 7,

f(9) = 8,

f(10) = 12,

<...>.

Мне интересно также узнать предел последовательности или предел последовательности отношений соседних значений функции.

На данный момент я знаю, как подсчитать количество способов соединить все вершины, соединить вершины так, чтобы граф разделился на две части, и соединить вершины так, чтобы граф разделился на 3 части.

Answer 1

Находим, что члены последовательности A002865 могут быть получены как разности соседей в последовательности количества разбиений A000041, а для неё есть алгоритм получения n членов за время O(n*sqrt(n)).

Используем подсказку из вики с применением пентагональных чисел:

def part2(n):
    n += 1
    np = [1] + [0]*n
    for i in range(1, n+1):
        sign = -1
        k = 0
        while True:
            sign = -sign
            k += 1
            pent = k*(3*k-1)//2
            if pent > i:
                break
            np[i] += sign*np[i-pent]
            pent = k*(3*k+1)//2
            if pent > i:
                break
            np[i] += sign*np[i-pent]
    return [np[i+1]-np[i] for i in range(n)]

print(part2(20))

По первой ссылке можно посмотреть другую интересную информацию о данной последовательности.

БЛОГ НА HUSL

Алгоритм нахождения кол-ва способов разложения натурального числа на сумму

Ответы (1 шт):