一类带对角步格路的组合恒等式
时间: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 , ， ,那么就有下面的组合恒等式 (责任编辑：qin) |