如何将给定代码转换为数学函数？

Question

我正在尝试将递归转换为数学公式。下面的代码片段 (c++) 是一个简化的变体。这些值看起来像一个指数函数，但我试图找到一个封闭的形式。例如，rec(8, 6)是1287。作为假设，我首先假设6是常数，并试图找到rec(?, 6)的指数函数。然而，这些结果极不准确。有谁知道我如何实现封闭功能？非常感谢

int rec(const int a, const int b, const int c = 0, const int d = 0)
{
  int result = 0;
  if (d == a)
    ++result;
  else
    for (int i = 0; c + i < b; ++i)
      result += rec(a, b, c + i, d + 1);
  return result;
}

Answer 1

没有将递归函数转换为数学封闭函数的通用方法。在您的情况下，答案是 the number of "b-1" combinations from an "a"-element set，即 a!/((a-b+1)!(b-1)!).

证明：你的rec等价于

int rec(const int a, const int b)
{
  if (0 == a)
    return 1;

  int result = 0;      
  for (int i = 0; i < b; ++i)
      result += rec(a - 1, b - i);
  return result;
}

因为重要的是 a-d 和 b-c。

如果a==0, rec returns 1

如果a>0，它returnsrec(a-1, i)的总和，其中i在(0,b)。这是正确的，并且仅适用于组合。如果你让我证明，我会的，但是纯文本格式不利于数学证明

编辑：一般思路：将所有 rec(i,j) 打印为 table 并尝试通过查看 [=40= 来发现规则].我做到了：

for (int i = 0; i != 10 ; ++i){
  for (int j = 0; j != 10; ++j){
    cout << rec(i, j) << "\t";
  }
  cout << endl;
}

这样我发现是Pascals_triangle

Answer 2

我会提示您如何自己猜出结果，并强调猜测。

取 rec(i, 6) 的序列，i = 0,...,10。这是您已经研究过的序列。答案是：

1 6 21 56 126 252 462 792 1287 2002

现在，将其插入Google（我不知道其他搜索引擎是否可以做到这一点；Google肯定可以）。第一个结果应该指向这个著名的在线百科全书：

https://oeis.org/A000389

这是整数序列的在线百科全书！现在，阅读说明：

A000389 Binomial coefficients C(n,5).

你可能不熟悉C(*,*)符号，但你可以很容易地理解它的“二项式系数”描述。

您当然注意到函数中的 6 和答案公式中的 5 之间的关系，但为了确保您可以对 6 以外的其他几个数字重复实验。

下一步是查看 A000389 序列的样子：

0, 0, 0, 0, 0, 1, 6, 21, 56, 126, 252, 462, 792, 1287, 2002, ...

好吧，如果 i < j，则 C(i,j) 未定义（或零，取决于约定）。啊哈！ A000389是这个：

C(0,5) = 0, C(1,5) = 0, ... , C(4,5) = 0, C(5,5) = 1, C(6,5) = 6,...

这是你的序列，如果你从索引 5 开始，如果我们从 0 开始计数。

res(0,6) = C(5,5), res(1,6) = C(6,5),..., res(k, 6) = C(5+k, 5)

你可以概括为

res(k, j) = C(k + j - 1, j -1)

然后开始思考如何用数学上严格的方式证明它。通常的方法是通过数学归纳法 - 我会跳过它。

这个最终结果已经由@Botond_Horwath给出了，我只是向大家展示一下Google搜索引擎+OEIS网站的神奇之处。（如果知道后者，前者就多余了）

如何将给定代码转换为数学函数？

How can I convert the given code to a mathematical function?

c++

mathematical-expressions