python - 从递归函数导出封闭形式

Question

给出了以下递归定义的函数，用 Python 编写:

def f(n, x, y):
    if n == 0:
        return (2*x)+(2*y)
    if n > 0 and y > x:
        return 0
    if n > 0 and x == 0 and y == 0:
        return 1
    if n > 0 and x > 0 and y == 0:
        return f(n-1, 0, f(n, x-1, y))
    else:
        return f(n-1, f(n, x-1, y-1), f(n, x-1, y))

当 x >= y 时，我被要求找到 f(1, x, y) 的封闭形式。

我发现每当 y = 0 或 x = y 时，该函数都会返回 2^x。我似乎无法找到适用于任何其他情况的公式(或扩展我已有的公式)。任何帮助将非常感激。

Answer 1

如果您尝试为 n==1 制作表格你得到:

for x in range(10):
    for y in range(x+1):
        print(f"{f(1, x, y):6}", end='')
    print('')

输出:

     1
     2     2
     4     8     4
     8    24    24     8
    16    64    96    64    16
    32   160   320   320   160    32
    64   384   960  1280   960   384    64
   128   896  2688  4480  4480  2688   896   128
   256  2048  7168 14336 17920 14336  7168  2048   256
   512  4608 18432 43008 64512 64512 43008 18432  4608   512

这看起来非常像帕斯卡三角形，但每一行都乘以 2^x。

所以，f(1, x, y) = 2**x * math.factorial(x) // (math.factorial(y) * math.factorial(x-y)) .

根据公式，通过归纳法证明应该不会太困难。

为了简化对函数f的理解，您可以为每个n制作一个单独的版本。仅作为n=0和n=1在问题中考虑，只需重写 f 给定固定 n :

def f0(x, y):
    return 2 * (x + y)

def f1(x, y):
    if y == 0:
        if x == 0:
            return 1
        else:
            return 2 * f1(x - 1, 0)
    elif y > x:
        return 0
    else:
        return 2 * (f1(x - 1, y - 1) + f1(x - 1, y))

很明显f1(x,0) = 2**x .

证明f1(x,y) = 2**x * x! / (y! * (x-y)!)的公式，假设对于较小的 x 来说已经如此，然后为 0 < y < x :

    f1(x,y) = 2 * (f1(x - 1, y - 1) + f1(x - 1, y))
or  f1(x,y) = 2 * (2**(x-1)*(x-1)! / ((y-1)! * (x-y)!)
                   + 2**(x-1)*(x-1)! / (y! * (x-y-1)!))
or  f1(x,y) = 2**x * (x-1)! * (1 / ((y-1)! * (x-y)!) + 1 / (y! * (x-y-1)!))
or  f1(x,y) = 2**x * (x-1)! * (y / (y! * (x-y)!) + (x-y) / (y! * (x-y)!))
or  f1(x,y) = 2**x * (x-1)! * (y+x-y ) / (y! * (x-y)!)
or  f1(x,y) = 2**x * x! / (y! * (x-y)!)

案例y=x需要单独考虑。计算结果如下:

    f1(x,x) = 2 * (f1(x - 1, x - 1) + f1(x - 1, x))
or  f1(x,x) = 2 * (2**(x-1)*(x-1)! / ((x-1)! * (x-x)!) + 0)
or  f1(x,x) = 2**x
or  f1(x,x) = 2**x * x! / (x! * (x-x)!)      as in the formula

另外，显然f1(0,0) = 1 = 2**0 * 0! / ((0-0)! * 0!)