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, at 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, at k = 2 and 3

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

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

p (5) = (1) + p (2) + (3) + p (5 4) + (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可以表示为所有正整数的和的方法总数。

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

但是不使用欧拉恒等式在python中,

Answer 1

对于相当小的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给出了最大分区

Answer 2

执行以下操作:

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)