Dec 12

今天翻看以前的日记,看到几个月前发现的一个斐波那契数列的递推公式:$F(2n)={F^2(n)}+{F^2(n-1)}$                       (公式二)

在这里Fibonacci数列为从0开始的这样一个序列:1,1,2,3,5,8,13,21 . . .,满足$$F(n+1)=F(n)+F(n-1)$$,n>0;

记得当时是在晚上睡觉的时候在想怎么把递归程序转换成非递归程序的时候,想到Fibonacci数列,然后就想到上面那个公式的。

看到这个公式,还真不知道当时是怎么想出来的,于是把以前的草稿纸都翻了一下,才终于找到怎么推导出来的(看来有了想法一定要记录下来才行啊),如下:

Apr 10

      写了组合生成函数 ,本来打算再写排列生成函数的,但是看到了一个讲生成函数的讲义,觉得非常的好,所以我也就不写了,不过文章太长了,就用图片分享给大家吧。文章是用繁体字写的,不过还好,不是很难认。

Apr 1

找出下面和式的化简形式:
n*1+(n-1)*2+(n-2)*3+...+2*(n-1)+1*n=?
(例如:1+2+3+...+n=n(n+1)/2)
 

Mar 28

      调和级数是指无穷级数1 + 1/2 + 1/3 + 1/4 + ...,即取遍所有正整数n所得到的Σ1/n。虽然n趋于无穷时1/n趋于0,但这个无穷级数却是发散的。一个经典的证明是,把1/31/4都缩小到1/4,把1/51/61/71/8都缩小成1/8,把1/91/168个数全部缩小为1/16,以此类推,这样就可以得到无穷多个1/2,它们的和显然是无穷大的。
    现在,让我们把所有的质数划分为若干个子集,其中质数p属于编号为floor(p/1000)的那个子集(floor()是取下整的意思)。现在,你可以用这样的方式来定义一个“部分的”调和级数:先选出一些质数集合出来,然后列出所有这样的数,它所有的质因子都落在你选的集合里。显然,这样的数有无穷多个,它们的倒数和就形成了一个部分调和级数。例如,选择编号为13的子集,我们可以得到一个无穷级数Σ1/n,其中n取所有这样的数,它可以表示为大于等于1000小于3000的质数的乘积。
    前面我们已经看到,选择所有的集合所构成的无穷级数是发散的。现在的问题是,要想得到一个发散的级数,最少需要选取多少个集合?

Mar 28

在提出「生成函数」的数学定义之前,我们先考虑几个简单的排列组合问题。(不知道怎么回事,发表这篇文章首页显示会有问题,搞了好久没找到问题,于是清空重新输入了一遍,并把所有公式都去掉了,用文本代替,首页显示终于没问题了,可能公式就得你费力看了)。

考虑恒等式:(1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ac)x^2+abcx^3

如将a,b,c 看作代表三个对象,它的右边是一多项式,其系数恰代表了将 a,b,c 作组合的各种可能。常数项1表示在三对象中一个都不取;x 的系数a+b+c 表示在a,b,c 中取一个的各种组合,即或取a,或取b,或取 cx^2 的系数ab+bc+ac 表取二个的各种组合;x^3之系数表示了三个皆取的唯一方法。在这里可能产生各种情形是用+号连接,同时发生之事件则用乘法(即符号并列)表示。 

又设有5个球 a,a,a,b,c,其中三个球a 完全一样,则恒等式: 

 (1+ax+a^2x^2+a^3x^3)(1+bx)(1+cx)= 1+(a+b+c) x+(a^2+a b+a c+b c) x^2+(a^3+a^2 b+a^2c+

a b c) x^3+(a^3 b+a^3 c+a^2 b c) x^4+a^3 b c x^5

其中 x^r的系数表示了选取r个的各种可能组合(1<=r<=5 ) 

在排列组合问题中,加法原则与乘法原则是大家熟知的两个法则。加法原则是讲如一事件可能发生情况有 m 种,另一种事件可能发生情况有 n 种,则这两种事件其一发生情况有m+n 种。乘法原则是讲如一事件可能发生情况有m种,另一事件可能发生情况有n种,则这两事件同时发生情况有mn种。我们在上面两例用到的是一种符号运算,它遵从这两法则。在第二个例子中,因子(1+ax+a^2x^2+a^3x^3)表示了或不取a,或取一个a,或取2a,或取三个a 的各种情况;而在第一个例子中,(1+ax)(1+bx)表示了如果 a , b 被允许同时选取时可能产生之各种情况。