本文主要是介绍「营业日志 2021.1.14」Zeilberger 老爷子的 T 恤上写了啥?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这是一张 Wikipedia 上找到的图。其中写的恒等式是这样的:
∑ k ( n k ) 2 ( 3 n + k 2 n ) = ( 3 n n ) 2 \sum_k \binom n k^2 \binom {3n+k}{2n} = \binom{3n}n^2 k∑(kn)2(2n3n+k)=(n3n)2
20 世纪 90 年代,组合学家 Wilf 和 Zeilberger 发展了组合恒等式机器证明的算法理论,即 WZ 理论。该理论彻底改变了组合恒等式与特殊函数研究的面貌。计算机科学大师 Knuth 认为该理论将数学中一些重要的部分从艺术转变成科学。在 1996 年,Wilf 和 Zeilberger 也因此项奠基性工作获得美国数学会的 Leroy P. Steel 奖。WZ 理论及其相关应用促进了组合数学与符号计算的交互。许多组合问题,如组合恒等式证明,格路计数问题,组合序列的同余、整除、单峰性质等等,可以借助符号计算的算法与软件得到解决或验证。
——组合恒等式机器证明中的 Wilf-Zeilberger 猜想的解决
不过其实这件 T 恤上的恒等式并不恐怖,让我们来简单推导一下。
∑ k ( n k ) 2 ( 3 n + k 2 n ) = ∑ k ( [ x k ] ( 1 + x ) n ) ( [ x n − k ] ( 1 + x ) n ) [ y 2 n ] ( 1 + y ) 3 n + k = [ x n y 2 n ] ( 1 + x ) n ( ( 1 + y ) + x ) n ( 1 + y ) 3 n = [ x n y 2 n ] ( 1 + x ) n ( 1 + x + y ) n ( 1 + y ) 3 n \begin{aligned} &\quad \sum_k \binom n k^2 \binom {3n+k}{2n}\\ &= \sum_k ([x^k](1+x)^n)([x^{n-k}](1+x)^n)[y^{2n}](1+y)^{3n+k}\\ &= [x^ny^{2n}] (1+x)^n((1+y)+x)^n(1+y)^{3n}\\ &= [x^ny^{2n}] (1+x)^n(1+x+y)^n(1+y)^{3n} \end{aligned} k∑(kn)2(2n3n+k)=k∑([xk](1+x)n)([xn−k](1+x)n)[y2n](1+y)3n+k=[xny2n](1+x)n((1+y)+x)n(1+y)3n=[xny2n](1+x)n(1+x+y)n(1+y)3n
接下来我们改为枚举第二个括号中的 y y y,就会得到
= ∑ k ( n k ) ( n + k n ) ( 3 n 2 n − k ) = ∑ k ( n k ) ( 3 n 2 n − k , n , k ) = ∑ k ( n k ) ( 2 n 2 n − k ) ( 3 n n ) = ( 3 n n ) 2 \begin{aligned} &= \sum_k \binom n k\binom {n+k}n \binom{3n}{2n-k}\\ &= \sum_k \binom n k\binom{3n}{2n-k,n,k}\\ &= \sum_k \binom n k\binom {2n}{2n-k} \binom{3n}{n}\\ &= \binom{3n}n^2 \end{aligned} =k∑(kn)(nn+k)(2n−k3n)=k∑(kn)(2n−k,n,k3n)=k∑(kn)(2n−k2n)(n3n)=(n3n)2
这篇关于「营业日志 2021.1.14」Zeilberger 老爷子的 T 恤上写了啥?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!