差分
Finite
Difference
今天很高兴再次拿回了我的《组合数学》，这本书确实出的不错，里面有很多实用的小结论，特别对计算机等学科有极大的帮助，之前，我也有列举一二，今天在此看到一个很不错的关于差分的性质。
Today,
I am so lucky that my Introductory Combinatorics back, which
help me a lot. It includes many theory of great use, especially for
the subject like Informatics and so on. In the past, I have
introduced some of them. Fortunately, today I got a new one. It’s
about finite difference.
组合数学
第四版 定理8.2.2:
Introductory
Combinatorics 4th Edition Theory 8.2.2:
定理：其差分表的第0条对角线等于
的序列的通项满足
的n的p次多项式。
对定理的解释在此不再赘述，直接说说它的用法。
引用书上的例子：
计算其差分：
1 3 17 49
2 14 32
12 18
6
由于hn是n的三次多项式，它的差分表0对角线是
1,2,12,6,0,0,…
由8.2.2知：
将hn写成这种表达式，是又便于计算hn的部分和的。
我们很容易得到8.2.3:
说到这，基本都是书上的内容，我想说的是，我们常常利用它的逆过程，换言之，在找规律的过程中，我们常常首先得到是差分表，而不是表达式。在我们得到差分表的时候我们能迅速得到通项，这就是8.2.2的魅力所在。随便找一个通项是二次函数的试一试，差分表无疑要比其他方法来的优秀一些。对于更加复杂的（更高次的多项式）通项，8.2.2的优势更加明显，因为我们可以把问题直接抛给计算机了，用了较为统一的求法，无疑给计算机编程减少了不少难度。
其次，是关于定理8.2.3的，同样，较为统一的算式更易计算机求解，当然，求组合数对于计算机也未必都是一件轻松活。然而，这对于一些数列的求和起到了明显的帮助。还是以书上的例题为例（我做了一次{n3}的求和，效果不错）。
令
计算差分：
0 1 16 81 256
1 15 65 175
14 50 110
36 60
24
0对角线是：0,1,14,36,24.
所以
当然，我知道这不一定是最好最快的方法，但毕竟这种方法比较直接，特别是对于运输快的人特别有优势，或是其他复杂的表达式，想必这对于等式的证明也或多或少用一定帮助。
总而言之，定理8.2.2个人认为对已知数列求通项的问题帮助较大，它与定理8.2.3同样对于计算机都将有出色的表现。然而，它的缺点就是计算量大，即便是它能提取较多的公因式，但是还是容易出错，例如0对角线的第一个数字是当n=0的时候取到的，这些细节是要注意的。
p.s. 国外的书果然好贵啊，太可怕了，我查了原版书Introductory
Combinatorics (4th Edition) (Hardcover)
在Amazon上的价格是$106.24，我买这本书的中文版却只花了￥45，还真是便宜啊…
0 comments:
Post a Comment