N应该划分多少个数字的总和

Question

整数分区：

4 = 4                 p(4,1) = 1
  = 1+3, 2+2          p(4,2) = 2
  = 1+1+2             p(4,3) = 1
  = 1+1+1+1           p(4,4) = 1

/max(p(4, k)) = 2，在 k = 2

5 = 5                 p(5,1) = 1
  = 1+4, 2+3          p(5,2) = 2
  = 1+1+3, 1+2+2      p(5,3) = 2
  = 1+1+1+2           p(5,4) = 1
  = 1+1+1+1+1         p(5,5) = 1

/max(p(5, k)) = 2，在 k = 2 和 3

和p(n) = Σp(n, k) for ∀k: 0<k<=n

p(4) = p(4, 1) + p(4, 2) + p(4, 3) + p(4, 4) = 1 + 2 + 1 + 1 = 5

p(5) = p(5, 1) + p(5, 2) + p(5, 3) + p(5, 4) + p(5, 5) = 1 + 2 + 2 + 1 + 1 + 1 = 7

为此我使用了欧拉恒等式p(n, k) = p(n-1, k-1) + p(n-k, k)

#p(n, k) = p(n-1, k-1) + p(n-k, k)
N = int(input())
p = [[0]*(N+1) for i in range(N+1)]
for i in range(N+1):
    p[i][1] = 1
    p[i][i] = 1
for n in range(2, N+1):
    for k in range(2, n+1):
        p[n][k] = p[n-1][k-1] + p[n-k][k]
print(sum(p[-1])) 
for x in p:
    print(x[1:])
    print(sum(x))

使用上面的代码我可以找到整数的分区：p(N) 即给定数字 n 可以表示为所有正整数之和的方式总数。

但是，现在我想找到 k 的最大 p(n, k) 值。

但是在python中没有使用欧拉恒等式。

Answer 1

执行以下操作：

N = int(input())
p = [[0]*(N+1) for i in range(N+1)]

maximum = 0
k_number = 0
ans = []
for i in range(N+1):
    p[i][1] = 1
    p[i][i] = 1
for n in range(2, N+1):
    k_number, maximum = 0, 0
    for k in range(2, n+1):
        p[n][k] = p[n-1][k-1] + p[n-k][k]
        if p[n][k] > maximum :
              maximum = p[n][k] 
              k_number = k
              n_for_max = n
    ans.append([n, k_number, maximum])
print(sum(p[-1])) 
for x in p:
    print(sum(x))
for x in ans:
    print(x)
#print('k_number: ',k_number)

Answer 2

对于相当小的 n 值，您可以隐式生成所有分区，计算每个分区中的零件数。

n = 7
kcounts = [0]*n

def parts(sum, last = 1, k=0):
    if sum == 0:
        global kcounts
        kcounts[k-1] += 1
        return

    for i in range(last, sum + 1):
        parts(sum - i, i, k + 1)

parts(n)
print(kcounts)

>>[1, 3, 4, 3, 2, 1, 1]

所以 k=3 给出最大分区数

N应该划分多少个数字的总和

Sum of how many numbers should N be partitioned

python-3.x

algorithm

math

dynamic-programming

number-theory