递推公式与筛法原理初等证明

1、4.5 递推公式与筛法原理初等证明我们从平面几何问题开始：平面上n条一般直线（即任何两条直线不平行，任何三条直线不相交于一点）把平面分成几个部分.令Pn表示此数。显然，由此得 下面我们研究n-样本的集合，其中只能取0和1；现在我们求具有下面性质的样本数：即不允许样本中连续出现两个0的样本例如（001）是不允许的。如果我们用f(n)表示此样本数，则有 设，如果n样本的第一个坐标，那么有个所要求的样本数；如果，那么必须为1。所以所需样本数为，所以有 f(n)就是递推公式。根据此公式得出的数列称为斐波那契数列。扰乱排列也可用递推公式算出。设Dn表示n个数码的扰乱排列总数，这时n个数码的扰乱排列分两种

2、情况。（1）第一个位置是数k,而第k个位置是数1，余下的n-2个数码应各不在自己正常位置，因而共有Dn-2种排列。（2）第一个位置是数k,而第k个位置不是数1，这相当于要求1,2, ,k-1,k+1, n这n-1个数码都不在自己的正常位置（1的正常位置是第k个位置）因而共有Dn-1种排列。由于k的选择有n-1种，所以这里D1=0，D2=1。如果S是n个数码1,2,n的集合，问从S中取k个数码，但不允许两个连续数码被取出（即取1就不许取2）的方法数有多少种？定理4.6 设f(n,k)表示从n个数码取k个数码（但不许取连续两个字码）的方法数，则证明 我们用归纳法证明，显然 从n个数码中取k个数码可

3、分两种情况：（1）取的数码没有1，这时所求的方法数为 （2）取的数码有1，（这时2能取）这时所求的方法数为 所以 按归纳假设 所以 现在我们用第二种方法计算上题：令1,2,n这n个数码排成一排，如果数码i被取出，则在i数码后面点一个逗点。这样，取k个数码需点k个逗点。设第1个逗点前有x1个元素，第2个逗点与第1个逗点之间共有x2个数码，第k个逗点与第k-1个逗点之间共有xk个数码，第k个逗点后面共有xk+1个数码，则由于要求没有连续两个数码被取出，所以由此得上式k+1个正整数的和是n+2-k,它的不同解的个数就是所求f(n,k).所以它实际是从n-k+2个点的n-k+1个空中取k个空的方法数，

4、即。定理4.7 设g(n,k)表示从n个数码中取k个数码，但不允许取连续两个数码（1和n算连续数码）的方法数。那么 证明 仍然分两种情况：（1）取出的数码有1，这时2和n都不能取，因而所取的方法数为 （2）取出的数码没有1 这时所取的方法数为所以 最后，我们用集合的方法给出筛法原理的初等证明。如果A，B，C，表示有限集合。|A|表示集合A的元素个数。那么显然有 如图4-1和图4-2所示。AB CBA 图4-1 筛法原理示意图（1） 图4-2 筛法原理示意图（2）定理4.8（容斥原理）设是有限集合S的子集合，则 |证明 当m=2,m=3时，定理显然正确。现在假设定理对mn正确，往证定理对m=n+

5、1成立。设 由归纳假设有 但是 所以 将此式代入（4-5-1）式即得定理的证明如果是有限集合S的子集，则此公式与筛法原理公式完全相同，因为可表示同时具有两个性质的元素集合个数，可表示同时具有三个性质的元素集合个数。例1 求不大于100而又能被2或者5，或者3，或者7整除的自然数的个数。解 设表示能被k整除而不大于100的自然数集合（k=2,3,5,7），这时 根据定理4.8 例2 由数字1，2和3组成n位数，要求n位数中1,2和3每个数字至少出现一次，求这样的n位数共有多少个。解 由数字1，2，3所构成的n位数共有|S|=3n个。设S中不含有数字1的n位数集合为A，S中不含有数字2的n位数集合为B，S中不含有数字3的n位数集合为C。则显然为所求集合。但是