毕业论文

打赏
当前位置: 毕业论文 > 数学论文 >

一类带对角步格路的组合恒等式

时间:2020-06-13 20:50来源:毕业论文
摘要 本文将一类经典格路中的组合恒等式推广到了带对角步的情形,给出了相应的组合恒等式.关键词 格路径;组合恒等式;对角步一、引言格路计数问题是组合数学中的一类重要问题

摘要 本文将一类经典格路中的组合恒等式推广到了带对角步的情形,给出了相应的组合恒等式.关键词 格路径;组合恒等式;对角步一、引言格路计数问题是组合数学中的一类重要问题. 50850
我们能够通过引入格路,对二项式系数的组合恒等式进行分析,并作出直观的几何解释. 进而,要想找到或证明一些组合恒等式,我们可以借助格路的几何性质进行研究.文献[5]中探讨的是从点   0 , 0 到点   n m, 的格路,其中允许的移动步伐可以是:水平步: ) , 1 ( ) , ( j i j i   ;垂直步: ) 1 , ( ) , (   j i j i . 本文考虑增加对角步: ) 1 , 1 ( ) , (    j i j i 的情形.若仅考虑带垂直步和水平步的路径的情况,从点  0 , 0 到点  n m, 的非降路径数可以用组合数  nn m来表示. 现允许增加对角步,那么把从点   0 , 0 到点   n m, 的非降路径数记作 nn m。考虑  nn m的计数如下:设在所有路径中对角步的步数为r ,由此可知从点  0 , 0 到点  n m, 的总步数是 r n m   .其中上移的步数是 r n  ,右移的步数是 r m  ,也就是说总的格路数为      ! ! !!r r n r mr n m  ,由于r 的任意性,对其求和,得到           n mr r r n r mr n m , min0 ! ! !!,即 nn m          n mr r r n r mr n m , min0 ! ! !!     n mr r r mmr nr n m, min0 ! !!     n mr r r nnr mr n m, min0 ! !!.二、平面格路中的一个组合恒等式引理 1 直线 c by ax l   : ,其中 , 0 , 0 , bn am c b a     则直线l 与从点 ) 0 , 0 ( 到点 ) , ( n m 的任意路径的交点数有并且只有一个.证明 考虑直线l 与点 ) 0 , 0 ( 和点 ) , ( n m 的关系. 由 0    c bn am , 0 - 0 b 0     c a 可知,直线l 将点 ) 0 , 0 ( 和点 ) , ( n m 分开,两点分别位于直线两边,所以直线l 与从点 ) 0 , 0 ( 到点 ) , ( n m 的任意一条路径的交点数都至少有一个. 现假设存在一条格路径P ,且直线l 与该格路径的交点数有两个或两个以上. 那么对这两个交点,我们令它分别是 ) , ( 1 1 y x 和 ) , ( 2 2 y x ,若假设格路径 P 通过这两点的顺序分别是先点) , ( 1 1 y x ,再点 ) , ( 2 2 y x ,这样我们就有 2 1 x x  和 2 1 y y  成立.同时因为点 ) , ( 1 1 y x 和点 ) , ( 2 2 y x都 满 足 直 线 l 的 方 程 , 所 以 我 们 有 c by ax   1 1 , c by ax   2 2 , 我 们 就 能 够 得 出02 12 1  bax xy y,这和 2 1 x x  和 2 1 y y  相互矛盾.所以假设不成立, 即不存在任何格路径P ,使它与直线l 的交点数同时有两个或两个以上.综上,对于从点 ) 0 , 0 ( 到点 ) , ( n m 的任意一条格路径P ,直线l 与该格路径的交点数有并且只有一个.引理 2 令 为包括以点 ) 0 , 0 ( 和点 ) , ( n m 为对角线的矩形内的全部步进的集合,要是集合的子集         k i y x w y x v w v e A i i i i i i i i i, , 3 , 2 , 1 , , , , | ,' '       满足条件:从点 ) 0 , 0 ( 到点 ) , ( n m 的任意一条路径P 都通过并且仅通过A 中的一个元素,那么就有如下组合恒等式成立:      '' '0 ii iki ii ix my x n mxy xnn m.证明 已知从点 ) 0 , 0 ( 到点 ) , ( n m 的任意一条路径P 都通过且仅通过A 中的一个元素,并且通过A 中的其中一个元素 ie 的格路径数为    '' 'ii iii ix my x n mxy x. 所以,通过 A 中各个元素的格路径数之和就是     '' '0 ii iki ii ix my x n mxy x,即所有的从点 ) 0 , 0 ( 到点 ) , ( n m 的格路径数.这里考虑带对角步的格路径,就是  nn m.所以       '' '0 ii iki ii ix my x n mxy xnn m得证.定理 1 如果实数 c b a , , 满足条件 bn am c b a     0 0 , , ,那么就有下面的组合恒等式 一类带对角步格路的组合恒等式:http://www.youerw.com/shuxue/lunwen_54286.html
------分隔线----------------------------
推荐内容