构造离散函数证明组合恒等式.pdf

8-432023年第8 期数学教学构造离散函数证明组合恒等式唐保祥（天水师范学院数学与统计学院，甘肃天水741001)表示组合数之间关系的恒等式称为组合恒等式，它们从一个侧面反映出整数的一些基本性质,其中有不少重要的组合恒等式已成为研究数论、级数和其他数学分支的基础.组合恒等式也是组合数学理论的重要组成部分。组合恒等式的证明往往有较强的技巧1-3.本文通过构造特殊离散函数,用两种不同的思考方法计算同一类特殊离散函数的个数，从而得到四个组合恒等式.先给出两个预备结论作为基础1子预备问题问题1已知集合A=（a 1，a 2，a mB=b1，b 2，b,，集合A到集合B的所有不同映射的个数为n。解：对任意一个映射f:AB,每个(a,)在B中选择像的方法都有n种（i=1，2，m），因为不同的像对应不同的映射，所以集合A到集合B的不同映射共有n个。问题2 设集合A=1，x 2，x l，B=y1,y2，y ml，n m1,由A到B的满射的个数为：m-1Z(-1)ici(m-i).i=0解：设A,是A到B的y；没有原像的所有映射的集合，i=1，2，m.由容斥原理和预备问题1的结论可知，由A到B的满射的个数为：IA,nA,n.nAmI214.1+Zm=mCIA;nA,Ii=11ijmIA,nA,nA.I+.1ijkn+(-1)|A,nA,n.nAm因为|A,|=(m-1)，I A,n A,l=(m-2),一般地|A,nAi,nA,|=(m-l),IAnA,n.nAm=O,所以A到B的满射的个数为：m-1Z(-1)ci(m-i).i=02组合恒等式及其证明n组合恒等式1：Zct n=(1+n).i=0证明：令集合A=1,2，n ,记A的i个元素的子集为A；，则数集A，到数集A的不同函数的个数为n，i=1，2，n.那么集合A的所有非空子集到集合A的不同函数的个数为nZcn.i1另一方面，可以用如下方法得到集合A的所有非空子集到集合A的不同函数的个数：令B=1,2，,n，n+1),对集合A的非空子集C到A的任意一个函数f:CA,定义函数g:AB为：g(=f(),当f()有定义时,Lg（）=n+1,当f(）无定义时.反之，对集合A到集合B的任意一个函数g:AB，定义集合A的非空子集C到A的函数为：f(x)=g(x),VxE C,其中C=(xEAlg(x)n+1).特别地，上述定义中包含了集合A的空子集到A的“函数”因此，集合A的所有非空子集到集合A的不同函数与集合A到集合B的函数是一一对应的.集合A到集合B的不同函数的个数为8442023年第8 期数学教学（n+1），故有组合恒等式：Z c,ni=(1+n)-1,即Zc,n=(1+n).i=0实际上，利用二项式展开公式展开（1+n）就可直接得到组合恒等式1.组合恒等式2：Z c (n-1)i=ni=0n2.证明：令集合A=a1，a 2，a n ,如果存在a;EA,使得映射f:AA满足f(a;)=a,则称f是有不动点的映射.下面用两种方法计算集合A到A的至少有一个不动点的映射的个数.设g是A到A的任意一个无不动点的映射,则 Va;EA,g(a;）a i,所以g(a,)只能取a1,a2，,a i-1,a i+1,，a,中任意一个元素,i=1，2，n.所以A到A的无不动点的映射共有（n1)个.于是,A到A的至少有一个不动点的映射的个数为n（n 1）。另一方面,A到A的所有不同的恰好有i个不动点的映射的个数为C,（n 1)-i（1in），所以得到一个组合恒等式：nZc,(n-1)i=n-(n-1),n 2.即nZc (n-1)-i=ni=0实际上，用二项式展开公式展开n=（1+（n 1）的右边可直接得到组合公式2.而且若规定0=1,则组合公式2 对于n=1也是对的.n-1组合恒等式3：Z(-1)ci-(n-1-i=0n(n-1)(n-2)!i）“=，n 3.2证明：令集合A=（x 1，x 2，x，B=(y1，y 2，y n-1，则由预备问题2 的结论可知,由A到B的满射的个数为：n-1Z(-1)ci-(n-1-i).i=0另一方面,A到B的任意一个满射f一定有某两个不同元素x，x（i j）对应同一个元素y（h=1，2，n 1），所以对应关系如图1所示.2Xn-1nyiyiyiyi图1其中yi，i z，,y i，y i a-y i,是yi,y2，y n-1的一个排列.由图1可知A到B的满射的函数个数为：C,C二(n2)!.所以n-1Z(-1)ci-I(n-1-i)i=0n(n-1).(n-2)!2注意：计算可知组合恒等式3对于n=1，2也是对的.n-3组合恒等式4：Z(-1)Ci-2(n-2-i=0(n-2)(3n-5)n!n4.24证明：令集合A=（x 1，x 2，x），B=(y1，y 2，y n-2 1，则由预备问题2 的结论知，由A到B的满射的个数为：n-3Z(-1)Ci-2(n-2-i).i=0另一方面，由A到B的满射有两种情形：情形1存在某三个数i，j，k 互不相等，使得x，这三个不同元素都对应同一个元素yi，对应关系如图2 所示.X2n-1Xnyiyiyiyiyiyin-2图28-452023年第8 期数学教学利用圆锥曲线系解决高考试题李振涛王淑玲（北京市顺义牛栏山第一中学，北京101301)1过直线交点的圆锥曲线系我们知道，平面内任意3点不共线的5点可以确定唯一的一条二次曲线，其方程可以用F(x,y)=ax+2bxy+cy+2dx+2ey+f=0(+b+c0）表示，圆锥曲线分为以下类型：（1）椭圆型（包括圆、点和虚椭圆）；（2）双曲线型（包括两条直线相交）；（3）抛物线型（包括两条直线重合或平行及两条虚平行直线）.当二次曲线退化成两条直线时，可以用这其中yi，Yi a，,u,y i-y i 是yi,y2，y n-2 的一个排列.对于情形1,由图2 可知，由A到B的映射个数为:C,C=(n-3)!两条直线建立相应的二次曲线系，求解一些圆锥曲线的问题,可以带来一个新的角度.定理1若直线l:A,x+Biy+C,=0及l2:Az+Bzy+C,=0与圆锥曲线C:F(x,y)=0有交点，则过交点的圆锥曲线系方程为：入f(x，y)+(A,x+Biy+C)(Azx+B2y+C2)=0.定理2 若直线li:A,x+Biy+C=0及l2:Azx+Bzy+C,=0有交点,l3:Agx+B3y+C,=0及l4:A4x+B4y+C4=0有交点,则过交点的圆锥曲线系方程为入（A,x+By+C）（A z x+Bz y+C2)+(Agx+Bsy+C,)(A4x+B4y+Ca)=0.情形2存在某四个数i，j，k，l互不相等，使得一对不同元素，都对应元素yi，另一对不同元素，,都对应元素yi，对应关系如图3所示.12ik1nnyiyiyinin-3n-2D9图3其中yi，Yi g,y i,，,yi，Yin-是y1，y 2，,y n-2 的一个排列.对于情形2,由图3可知,由A到B的映射个数为:C,C-2Cn=(n-4)!.所以n-3Z(-1)ici-2(n-2-i)0C,Cr=(n-3)!+C,C-2Cn=(n-4)!(n-2)(3n-5)n!24注意：计算可知组合恒等式4对于n=3也是对的.参考文献1唐保祥,赵宇航，张蒙.有限数集上三类函数的计数J.天水师范学院学报，2 0 17，37(5):1-2.2唐保祥.有限集上不动点变换的计数J.中学数学教学参考（下旬）,2 0 15（12）：188-189.3唐保祥.两种排列的计数J.数学通讯,2 0 0 7(5):31-32.