将 n 写成 k 个数之和的多种方式

Question

所以我有这个公式：

P(n, 1) = P(n, n) = 1

P(n + k, k) = P(n, 1) + P(n, 2) + ... + P(n, k)

但是我看不懂

我写错了吗？我不明白为什么 P(n + k, k)

中有“n+k”

假设 P 是一个函数，我调用 P(6, 2)。 P(n + k, k) 有什么作用？它会转换为 P(8, 2) 还是 P(4 + 2, 2)...

我不明白它是如何工作的，也许如果有人给我一个例子，一步一步...

Answer 1

两行公式是数学定义，不是编程算法。希望他们提供足够的信息，以便您可以找出任何 P(x,y).

的值

由于第一行有效地定义了两种不同的情况，我想重写公式：

(A) P(n, 1) = 1

(B) P(n, n) = 1

(C) P(n + k, k) = P(n, 1) + P(n, 2) + ... + P(n, k)

所以，如果你想将它们应用到 P(6,2)，那么只有 (C) 可以匹配，因为 (A) 只能匹配 P(6,1) 和 [=16] =] 到 P(6,6).

之类的东西

P(6,2) 与 P(n+k,k) 的匹配意味着 k 必须是 2，而 n+k 必须是 6，给出 n=4.

然后 (C) 的右侧扩展为 P(4,1) + P(4,2)。它的第一部分与 (A) 匹配，第二部分与 (C) 匹配。因此，第一部分给出 1，第二部分必须以与 P(6,2) 相同的方式展开。等等...

如果您要实现计算 P(x,y) 值的函数，直接的方法是将定义公式转换为递归计算。

Answer 2

嗯，你必须一次又一次地应用公式:

   P(6, 2) = P(4 + 2, 2) = P(4, 1) + P(4, 2)

现在P(4, 1)我们有

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

借助归纳我们可以证明P(N, 1) = 1当N >= 1

对于P(4, 2)，我们有

   P(4, 2) = P(2 + 2, 2) = P(2, 2) + P(2, 1) = 1 + P(2, 1) = 
           = 1 + P(1 + 1, 1) = 1 + P(1, 1) = 1 + 1 = 2

终于

   P(6, 2) = P(4 + 2, 2) = P(4, 1) + P(4, 2) = 1 + 2 = 3

一般情况下（再次归纳）P(2 * N, 2) = N

最简单的 C# 实现（不适用于某些输入，例如 P(0, 1)）：

private static Dictionary<Tuple<int, int>, int> s_Cached = 
  new Dictionary<Tuple<int, int>, int>();

private static int P(int n, int k) {
  if (n == k)
    return 1;

  if (s_Cached.TryGetValue(new Tuple<int, int>(n, k), out var value))
    return value;

  int result = 0;

  for (int i = 1; i <= k; ++i)
    result += P(n - k, i);

  s_Cached.Add(new Tuple<int, int>(n, k), result);

  return result;
}

测试

Console.WriteLine(P(6, 2));

将 n 写成 k 个数之和的多种方式

Number of ways to write n as a sum of k numbers

algorithm

math

partitioning

sum

formula