（基础数学专业论文）二项式系数恒等式的q模拟.pdf

大连理工大学硕士学位论文 摘要 既是扎元集合 1 ，2 ，扎】的所有子集组成的布尔格，( g ) 是q 元有限域g f ( q ) 上的礼维向量空间，厶( 口) 是由( g ) 的所有子空间构成的子空间格布尔格玩与子空 间格厶( g ) 之间的口- 模拟是指把布尔格玩上的一些性质和恒等式推广到子空间格厶( g ) 上，在子空间格厶( g ) 上找到它们的口- 模拟形式，其中g 是参量，当q 一1 时，g - 模拟 趋向于布尔格既上相应的性质 恒等式的组合证明赋予了恒等式一定的计数意义，组合证明最常用的方法是通过构 造两个集合之间的双射，这两个集合的个数分别表示恒等式的两端，从而根据双射的一 一对应性证明恒等式本文也正是采用了这种方法对恒等式进行组合证明 本文给出了一些重要的二项式系数和高斯系数恒等式的组合证明，其中突出的成果 是给出了三个求和公式的口- 模拟及其组合证明 文章主要内容可概括如下： 1 介绍了一些与二项式系数恒等式的g - 模拟有关的基本知识，如：偏序集，格，组合 证明，二项式系数等 2 给出了一些经典的二项式系数恒等式及其组合证明 3 引入g - 模拟的概念，给出了一些二项式系数恒等式的g - 模拟及组合证明，并介绍了 子集子空间模拟的一般方法及多重集上的m a h o n i a ns t a t i s t i c 4 给出了三个求和公式的铲模拟及组合证明 关键词：二项式系数恒等式，布尔格，子空间格，口_ 模拟，组合证明 口- a n a l o g o fb i n q ) m i a lr e c i q ；n tidentitienalou e so tb i n o m i a lc o e l l i c i e n ti d e n t i t i e s俨 a b s t r a c t l e t 玩b et h eb o o l e a nl a t t i c eo fs u b s e t so fa nn - e l e m e n ts e t _ 【1 ，2 ，佗 ，a n d ( g ) a n - d i m e n s i o n a lv e c t o rs p a c eo v e rt h ef i n i t e f i e l dg f ( q ) w i t hqe l e m e n t s ，c n ( 口) i t sl a t t i c eo f s u b s p a c e s t h eq - a n a l o g u eb e t w e e n 厶( 口) a n d 玩m e a n st h a ts o m eq u a l i t i e sa n di d e n t i t i e so n t h eb o o l e a nl a t t i c e 魄a r ee x t e n d e do n t ot h el a t t i c eo fs u b s p a c e s 厶( g ) ，t h e nt h e i rq - a n a l o g u e s a r ed i s c o v e r e do nt h el a t t i c eo fs u b s p a c e s 厶( g ) ，w h e r eqi sa np a r a m e t e r w h i l et a k i n gt h e l i m i tq 一1 ，t h eq - a n a l o g u e sb e c o m ec o r r e s p o n d i n gq u a l i t i e so nt h eb o o l e a nl a t t i c e 既 b yt h ec o m b i n a t o r i a lp r o o f ，t h ei d e n t i t yi se q l l i p p e dw i t hc e r t a i nc o u n tm e a n i n g t h em o s t g e n e r a lw a yi nt h ec o m b i n a t o r i a lp r o o f si st oc o u n tt w os i d e so ft h ei d e n t i t yb yt w od i f f e r e n t m e t h o d s g e n e r a l l y , t h r o u g hb u i l d i n gab i j e c t i o nf r o mo n es e tt oa n o t h e ro n e ，t h en u m b e ro f t h et w os e t sr e s p e c t i v e l yr e p r e s e n t st h et w os i d e so ft h ei d e n t i t y b e c a u s eo ft h eo n e - t o - o n e p r o p e r t yo fb i j e c t i o n ，t h ei d e n t i t yi sp r o v e d t h i st h e s i sj u s ta p p l i e st h i sm e t h o dt og i v et h e c o m b i n a t o r i a lp r o o fo fi d e n t i t i e s i nt h et h e s i ss o m ec l a s s i c a li d e n t i t i e sw i t hb i n o m i a lc o e f f i c i e n ta r eg i v e nw i t ht h e i rc o m b i n a - t o r i a lp r o o f , a n dt h eq - a n a l o g u e so fs o m ei d e n t i t i e sa r eo f f e r e dw i t hc d r r e s p o n d i n gc o m b i n a t o r i a l p r o o f so nt h el a t t i c eo fs u b s p a c e s e s p e c i a l l y , o n er e m a r k a b l er e s u l ti st h a tq - a n a l o g u e so ft h r e e b i n o m i a lc o e f f i c i e n ti d e n t i t i e sa r eo b t a i n e dw i t ht h e i rc o m b i n a t o r i a lp r o o fo nt h ev e c t o rs p a c e t h em a i nc o n t e n to ft h i st h e s i sc a nb es u m m a r i z e da sf o l l o w s ： 1 i n t r o d u c es o m eb a s i ck n o w l e d g ea b o u tt h eq - a n a l o g u e ，s u c ha sp o s e t ，l a t t i c e ，c o m b i n a t o r i a l p r o o f , b i n o m i a lc o e f f i c i e n ta n d s oo n 2 s o m ec l a s s i c a li d e n t i t i sa r ep r o v i d e dw i t ht h e i rc o m b i n a t o r i a lp r o o fo nt h eb o o l e a nl a t t i c e 既 3 i n t r o d u c et h ec o n c e p to fq - a n a l o g u e q - a n a l o g u e so fs o m ec l a s s i c a li d e n t i t i e sa r eg i v e nw i t h t h e i rc 姆m b i n a t o r i a lp r o o f so nt h ev e c t o rs p a c e w ea l s oo f f e rag e n e r a lm e t h o do fs u b s e t - s u b s p a c ea n a l o g ya n di n t r o d u c et h em u l t i s e tm a h o n i a ns t a t i s t i c s 4 q - a n a l o g u e so ft h r e ei d e n t i t i e sa r eo b t a i n e dw i t hi t sc o m b i n a t o r i a lp r o o f so nt h ev e c t o r s p a c e k e yw o r d s ：b i n o m i a l c d e f f i c i e n ti d e n t i t y , b o o l e a nl a t t i c e ，t h el a t t i c eo fs u b s p a c e s ，q - a n a l o g u e ， c o m b i n a t o r i a lp r o o f i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作及取得研究 成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写的研究成果，也不包含为获得大连理工大学或其他单位的学位或证书所使用过 的材料 作者签名： 加o g ，s 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解”大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 作者签名： 导师签名趔! 型窭年b 且日 大连毽工大学硬女学位论文 1 引言 本研究课题所属的研究领域是组合数学组合数学，又称为离散数学，有时人们把 组合数学和图论加在起称为离散数学，它是计算机出现以后迅速发震起来的- - 1 7 数学 分支计算机科学是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象 的处理就成为计算机科学基础理论的核心，而研究离散数据的科学恰恰就是组合数学 组合数学不仅在基础数学和计算杌科学的研究中具有极其重要的地位，在其它的学科孛 也有重要的应用，如运筹学、生物信息学、编码和密码学、物理、化学等学科中均有重要 应用组合数学的研究领域有很多，如；计数组合学，代数组合学，匿论及其算法，组合 优化，组合设计等等 本课题所属的研究方向是计数组合学中恒等式的q - 模拟及其组合证明，它对于组合 数学的研究有菲常重要的意义，赋予了恒等式一定的计数意义，而且与经典分析、线性 代数以及抽象代数相联系，一直以来都深受组合数学家们的重视 g o l d m a n 和r o t a 1 4 i 于1 9 7 0 年开始对子空间格和礼元集上的布尔格之间模拟做系统 性地研究，他们给出了一些铲恒等式在子空间格上的组合解释，并说明当q _ 1 时就是 二项式系数恒等式k n u t h 1 8 1 于1 9 7 1 年指出q 元有限域上的n 维向量空间的任何一个 k 维子空闻都有唯一的一组满足一定条件的有序基m i l n e z 3 予1 9 8 2 年给蹬了一些从子 空间格到n 元集上的布尔格的保序映射之后王军【2 8 】予1 9 9 9 年在保序映射的基础上构 造了从子空间格的某一商格到布尔格的嗣构映射，从而揭示了可以在子集格和子空间格 之闻做争模拟的蒙因随后，冯红 1 翻把m a h o n i a ns t a t i s t i c 推广到多重集上。1 9 9 2 年， y c c h e n 和r o t a 7 给出了包含排除原理在子空间格上的口- 模拟在p d o r d a n 2 5 , p 0 5 】中， 有如下两个恒等式 耋( 釉( 糟二惫) 一( 蒜) 薹( 一k ) ( 珏二? = ( 靠王) 类似地，我们可以得到如下恒等式 k = 一l r - k ) 嚣( 嚷1 ) 本文将给出以上三个求和公式的g 模拟，并在予空间格上给出相应的组合证明由此可 以得到w a m a a r 2 9 在2 0 0 4 年给出的关于翦n 顼整数和的经典求和公式的一个孥模拟 王 大连瑾工大学i 奚士学位论文 2 预备知识 本文主要从向量空间角度给出了一些恒等式的g - 模拟及其组合证明，首先我们介绍 一些与之糖关的基本知识和基本概念 2 。1 偏序集 偏序集是一种特定的集，它是一类主要的序关系集，具体地说，集合e 连同其上地 偏序r 构成地关系集( e ，固，一般记为p = ( e ，) ，所谓偏序( 或序关系) 是一类具有自反 性，反对称性和传递性地二元关系，例如，数之间地不大于关系，宣然数之间地整除关 系，集合之间地包含关系等把集合霹的基数称为偏序集p 的阶，阶为有限值的偏序集 称为有限偏序集丽在p 上，对于任意元素。，y ，区闯k ，翻均势有限偏序集时，称p 为 局部有限偏序集这两类偏序集是组合理论中的主要研究对象偏序集上所有链的长度 的最小上界或上确界，称为偏序集的长度，记为z ( p ) 。 偏序集的最大元，最小无： 偏序集p = ( e ，) 的子集s 中的元素a ，若在s 中不存在其它元素$ ，使得agz ，则 称a 为s 上的极大元对称地，若在s 申不存在其它元素$ ，使得。a ，剐称a 为s 上 的极小元若取s e ，则分别称a 为偏序集p 的极大元，a 为偏序集p 的极小元当 p 为有限偏序集时，其极大元，极小元总是存在的，若对于p 的所有元素x 均有搿a ， 则称a 为偏序集p 的最大元。对称地，若对予p 盼所有元素。均有a z ，则称a 为偏 序集p 的最小元偏序集并不总有最大元，最小元着它时有限全序集，则它总有最大 元和最小元 2 2 格 格是一类代数结构它是建立在偏序集p 一( e ，s ) 之上的，由e 的任意元素$ ，y 构 造的如下两个集合1 ( z ，y ) 一 名elz z ，y z 及2 ( 。，秒) 一 名e1 名z ，z 办 它嬲作势夕鳃子集均为偏序集，一般不一定有最大元或最小元若对p 的任意元素z ，y ， l ( z ，y ) 均有最小元，2 ( z ，y ) 均有最大元，则称p 为格，并记为c 在格上，把l ( 茹，y ) 和其最小元的对应关系视为一类二元运算，称为x 和y 的交， 记为。a y 对称地，把飓( 茹，y ) 和其最大元的对应关系视为和y 的结，记为。v y 它 们是格上地最基本的运算这两类运算满足： ( 1 ) 同一律茹v 髫= x ；xa 鬈= 善。 ( 2 ) 岑芒彰延律茹vy = y v z ；zay = y ao 3 ( 3 ) 结合律茹v ( yv 名) = ( 霉vy ) vz ；a ( yaz ) 燃( $ ay ) a 岩 ( 莲) 吸浚律x a 白vy ) = 鬈v ( 霈a y ) 一鬈，其中就y 帮2 均为雾的任意元素，墓诧格又 可视为满足上述四条规律的代数结构c 然( e ，v ， ) 虽然格的理论建立较晚，大约在2 0 世纪3 0 年代左右，但是很快就在解决序集问题和组合问题及代数问题中迅速发展，成势 有关研究盼有效理论基础与一般具有序特征的代数结构不阕的是，格孛元素的序特征 不是外在的，而是内在的这是由于它们的序关系完全可以等价地又格地内在运算来刻 薄；茹冬y 警且仪当x v y 嚣y 或者y 巍且设当x a y = g 。送也反映了捺建交运算和结 运算地对称性有些重簧的格的例子例如，b 黧( 2 露，) 是格，这里2 露为霹的所有子 集的构成的集族，而leb 妃，其上的结运算劣vy 为集z 和集y 的并集，交运算。ay 为 集2 和集y 的交集。又船，若鲁然数嚣的所有正整除数缀戚集合e ，露鳇元素若，y 有序羡 系x r y 躺且仅籀韶能整除y ，则偏序集为p 然( e ，r ) 格，茹vy 为z 和y 的最小公倍数， 茹ay 为霉露y 的最大公约数。 2 3 映射及组合证明 设歹( 鸠) 或n m 为掰到的映射，的集合：对于每一个嚣m ，通过歹就对应 到z 的象y n ，记为y 一，( z ) 我们通常写，：ml 一来代替f j ( m ，) ，当m 和 帮有限时，m 一| m | ，n = | n | ，我船可以绘掰的元素编号，设m = 魏，黝， ， 显然，给一个，就等价于给一个的m 个元素的袭，比方说， 可l ，纨，它们依 菜一顺序，允许重复地列出。那么所谓绘出这个表就意味着y i 是魏( 1 冬ism ) 的象t y i = ，( 茹1 ) 换句话说，绘一个歹就等价予绘出一个属于y m 酶m 元组，也称势一个m - 选择这样，就找到了把j ( m ，n ) 记为n m 的理由 蓦l 理2 1 。有限个有限集合的乘积纂台爵元素个数满足； mm l 越| 燃l 赎矧姨| | 越| 1 | 一l i - - - - 1 证明： 事实上，胁元组锄，y 2 ，辣 妤个数等于镌中y l 的哥麓选择数| 瓤| 慕以拖 中y 2 的可能选择数l 飓 ，等等，乘以a k 申的可能选择数1 “( 因为这些选择是 摆互独立的) 由这个孳l 理容易证得下面这个定理。 定理2 1 m 到的映射个数有下式给出： ( 配) = i 艇| - | nl i m l 。 对每一个予集acm ，我们表示 f ( a ) ：= ，( z ) l 。毫a 这样就定义了个扶b ( m ) 裂联) 蠢l 鹭映射，黎鸯，囊魁的子集集合上翦扩张。这也 用，袭示其中黟( 瑟) ，b ( n ) 分别表示耐，的所有子集构成的集合 莲 大连理工大学硕士学位论文 对所有y n ，m 的子集 f - 1 ( ) ：- - - zi ，( 。) = y ) 可以是空的，称为由，得到的y 的原象或逆象 定理2 2 m 的子集个数，包括空集，由下式给出； 召( m ) = 2 i m i 证明： 设是具有两个元素0 和1 的集合，我们把子集acm 等同于由z a ，f ( x ) = 1 ， 否则，( 。) = 0 所定义的从m 到的映射，( 通常称为特征函数) ，这样，就建立了集合 b ( m ) 到n m 的一个一一对应，其中n = o ，1 ) ，因此b ( m ) 与n m 有相同的元素个数 n i i m i - - 2 m i 得证 下面我们介绍什么是组合证明，首先，我们回忆一下代数学中的知识， ( 1 ) 如果两个不同元素的象也不同：x l x 2 争f ( x 1 ) f ( x 2 ) ，n m 就称为是单 射的( 或叫做一个单射) ； ( 2 ) 如果的每个元素都是m 中某一元素的象：v y n ，j z m ，使得，( z ) = y ， 就称为满射的( 或叫做一个满射) ； ( 3 ) 如果，既是单射的又是满射的，就称为双射的( 或叫做一个双射) 在( 3 ) 这种情况下，的逆或反，记为厂1 ，定义y = 1 - 1 ( z ) 当且仅当z = ，( y ) ，这里 z m y n 要数一个有限集合e ，换句话说，确定其大小，原则上就是建立e 到另一个元素个 数已知的集合f 上的双射；从而iel = lfi ，这也就是计数问题中所谓的组合证明 下面举一个组合证明的简单例子， 例设e 为的所有偶数个元素的子集的集合，f 为其余子集( 具有奇数个元素) 的集合，我们可选择z n ，建立如下的e 到f 的双射：根据。不属于a 或z a ， f ( a ) = au z ) 或a z ) ，因此，iel - lfl = ib ( n ) | - 2 犷1 2 4 二项式系数 对于每一个不小于1 的整数k ，我们记： 嘲k ：= 1 ，2 ，忌) 定义2 1 集合的一个k 一排列a ( 1 k n = ini ) 就是一个从【k 】到的单映射a ，我 们用h k ( n ) 来表示的k 排列的集合 因此，给出这样一个a ，首先等价于给出的k 个元素的子集 b = o ( ) = o ( 1 ) ，o ( 2 ) ，口( 尼) ) 其次，等价于给出了b 的元素一个从1 到k 的编号， 最后，等价于给出了的k 个元素的全部排序的子集，也经常叫做的一个舡排 列 5 定理2 3 n 的七一排列个数( 1 惫n = ini ) 等于 | 讯( ) | 一( 札) j c = 张( 绍一1 ) ( 纷一k + 王) 证明： 显然，l ( e 渊) 的象8 ( 王) 有耗种可能选择；8 ( 1 ) 选定后，因为a 是单射的，a ( 2 ) 8 ( 1 ) ； a ( 2 ) 就只有余下的一1 ) 中可能；类似地，因为a ( 3 ) o ( 2 ) ，a ( 3 ) a ( 1 ) ，对a ( 3 ) 只有 ( r , 一2 ) 种可能地选择，等等；最后，对8 ，恰有余下国一k 1 ) 种可麓的选择。 因此，a 的个数等于所有这些选择数的乘积，即等于 霸耗一1 ) 霸一2 ) ( 露一k + 圭) 。 注：如果庇 佗，则( n ) k = 0 定义2 2 。集合辑置换就是列自身的双射，我们月a ( n ) 表示的置换集合 定理2 4 ( inf 一佗1 ) 的置换个数等于扎! 证明： 仿照上面定理的证法易得证。 定理2 5 用b ( n ) 来表示n 的k 子集的集合，n 的k 子集个数用( 为来表示，则 ( 力一愀) | = 警= 业尘# 型 一茄与= ( 挖：惫)。顽再可2k 一惫夕 证明： 首先证羁等式( 参一| 器( 奶| 端警，其它几个都是它的誊接推论，如果k ；0 ，剥 警= 1 由于i 层( ) 1 只含n 的空子集，从而l8 ( ) i - 1 假设k 1 ，每个排列a u k ( n ) ，对应着b = ，( 8 ) = 8 ( 1 ) ，穗( 2 ) ，a ( 是) ) l 墩( ) l ，则 ，是u k ( g ) 到壤( ) 的映射，使得对所有b 玩( ) ，有 l 厂1 ) | _ 蹦 因为b 有惫! 种可能的编号现在当b 跑遍魄( ) 时，互不相交的原象集合厂1 ( b ) 完全 覆盖了讯( ) 。因此，魄( ) 的元素个数等于所有l 厂1 ( b ) | 的和，这里b 魄( ) ，即 有： ( n ) 知= l 敞( ) l - l 厂1 ( b ) i 燃南! l 玩( ) i 百 因此， 玩( ) l - 警得证 定义2 3 整数( ：) 叫做二项式系数 6 大连理工大学硕士学位论文 3 一些经典的二项式系数恒等式 上一章，我们介绍了组合证明的概念以及思想方法，并引入了二项式系数( ；) 这一 章将给出一些经典的二项式系数恒等式及它们的组合证明，通过这些例子将使我们进一 步理解组合证明的思想和方法 3 1 布尔格及子集格 布尔格是一种特殊的格，它是与布尔代数b = ( 2 e ；u ，n ) 同构的格，布尔格的结运算 和交运算分别对应于布尔代数的并运算和交运算 这里所说的布尔代数，是布尔( b o o l e ，g ) 于1 8 4 7 年及1 8 5 4 年研究推理规律( 逻辑 学，数理逻辑) 是提出的，而它作为一种特殊的格则是戴德金( d e d e k i n d ，j w r ) 后来提出 的所谓布尔代数，是指一个有序的四元组( b ；a ，v ，) 其中b 是非空集合，a 和v 分 别是b 上的二元运算，而“是定义在上的一个一元运算，并且满足下列条件：对于任 意a ，b ，c b ( 1 ) aab = b aa ；avb = bva ( 2 ) aa ( bac ) = ( 口ab ) ac ；av ( bvc ) = ( avb ) vc ( 3 ) a a ( a v b ) = 口；a v ( a ab ) = a ( 4 ) ( a ab ) v ( b c ) v ( c a a ) = ( a v a ( b v c ) a ( c v n ) ( 5 ) ( 口aa 7 ) vb = 6 ；( ava 7 ) ab = b 1 9 0 4 年，亨廷顿( h u n t i n g t o n ，e v ) 发现：若集合a 有一个二元运算v 和个一元运 算7 ，定义a ab = ( a t v6 ，) ，并满足： ( 1 ) a vb = b v n ； ( 2 ) ( nab ) v ( a 6 ，) = n ； ( 3 ) av ( bvc ) = ( ovb ) vc ； 则a 是布尔代数这是布尔代数的一个典型结果1 9 6 7 年，1 9 6 8 年戈莱兹( g r a t z e r ，g ) 和莫肯济( m c k e n z i e ，r n ) ，塔尔斯基( t a r s k i ，a ) 分别独立地进一步发现布尔代数可仅用一 个恒等式来定义 定义3 1 2 m 为扎元集合f 1 ，2 ，n ) 的所有子集构成的集族，按照包含关系“ ， b = ( 2 毗) 是子集格，简记为魄，其上的结运算zvy 为集z 和集y 的并集，交运算 zay 为集z 和集y 鸶交集 7 3 2 一些重要的二项式系数恒等式及其组合证明 一般二项式系数 ( ：) = 坐共k ( k 铲1 1= 菥， ( 3 2 1 ) 尼一) 庇! ( n 一七) ! r 叫 可以表示佗元数集 1 ，2 ，佗) 的k 子集的个数关于一般二项式系数( 彩有一些重要的 恒等式如下： 注：这些恒等式根据二项式系数的定义及归纳法可容易证明，这里只给出它们的组 合证明或组合解释 下面的证明中，用m 表示集合 1 ，2 ，凡) 定理3 1 仁项式定理) 设x y = y x ，对于每一整数竹0 ，我们有： c 咖卜壹k = o ( 扩厂七 = “( 护q 妙+ ( 笏扩2 “+ ( n 二1 ) 矿1 w 证明： 首先考查下列展开式系数伉，z ： + 耖) n = 毋岛r = 川x k y 。，其中只= x + y ，i h ，项扩是通过选择n 个因子只g i n ) 中的惫个，用克个因子中的“矿项乘以余下 ( n k ) 个因子中的“y 项而得到的，所以z = 礼一惫因此系数c k 。z = 瓯，n k 等于在礼个 因子中选出七个不同因子只的选择数为( 2 ) 即原式成立得证 例1 ：如果z = y = 1 ，那么o ( z ) = 2 n ，因此 1 ，2 ，n ) 的子集总数为2 n 例2 ：如果z = 一1 ，y = 1 ，那么毛o ( 一1 ) 七( 嚣) = 0 ，换句话说，集合 1 ，2 ，佗) 的偶 ”子集与有”子集一样多 定理3 2 恒等式3 2 j ( 凳) = ( n 二庇) 证明； ( ：) 表示n 元集合m 的所有k 元子集的个数，( n ! 七) 表示所有n k 元子集的个数， 设a 是任一个k 元子集，则a 关于集合 礼】的补集a 是礼一k 元子集，即：每一个尼元 子集对应一个n 一元子集反过来，每一个n 一惫元子集也对应一个七元子集，所以 的所有k 元子集与所有礼一七元子集存在一一对应关系，从而( ：) = ( 忆兰凫) 定理3 3 恒等式3 2 2 ( 北) = ( 撇二。1 ) 8 大连理工大学硕士学位论文 证明： 设a 是佗元集合 礼】的一个k 元子集，bca 是a 的一个z 元子集，则( 翟) ( ；) 表示 所有集合对( a ，b ) 的个数，令s = ( a ，b ) ) ， si = ( ；) ( ：) 设c 是礼元集合【叫的一个z 元子集，b 是m c 的一个七一2 元子集，令t = ( c ，d ) ) ，itf = ( ? ) ( n 七一- 1 1 ) 下面建立s 与t 之间的一个映射，：( a ，b ) 一( b ，a b ) ，则逆映射厂1 ：( c ，d ) 一 ( c + d ，c ) ，所以，是一个双射故isi = ( ：) ( ；) = iti = ( ? ) ( , 知r i m ) 得证 定理3 4 恒等式3 2 3 俨o s 2 - 三角j ( z ) = ( 十( n ：1 ) 证明： ( ：) 表示n 元集合【n 】的所有k 元子集的个数，分两种情况： ( 1 ) 彪元子集包含n ，取 1 ，2 ，礼一1 ) 中任一七一1 子集b ，bu 凡 是 仡】的庇子 集，共有( n 凫一- 。1 ) 个 ( 2 ) 忌元子集不包含扎，这时取 1 ，2 ，佗一1 ) 的一个七子集，也是 礼 的后子集， 共有( n i l ) 所以，( ：) = ( 凳二；) + ( n i l ) 得证 定理3 5 恒等式了2 4 ( v a n d e r m o n d e 一恒等式j ( n ：6 ) = 壹i - - - - 0 ( 一a ) ( 勿 证明： 我们知道o + b 元集合如l ，n 2 ，礼。，m l ，m 2 ，m 6 ) 的礼子集的个数为( a + 6 ) ，现在 我们用另一种方法来计算它的m 子集的个数，先从 扎l ，n 2 ，n 口) 选死一i 个元素，有 ( n 兰t ) 种方法，然后从 m 1 ，m 2 ，m b ) 中选余下的i 个，有( 种方法，对i = 0 ，1 ，2 ，n ， 求和得到伽子集个数为墨o ( n 兰。) ( ，因此 成立得证 ( 口：6 ) = 妻i = 0 ( n 二i ) ( 9 9 大连理工大学硕士学位论文 4 一些经典的高斯系数恒等式 通过前面的章节，我们已经对恒等式的组合证明有了个深入的了解，并能基本掌握 组合证明的方法，这一章将主要讨论子空间格上恒等式的g - 模拟及其它们在向量空间上 的组合证明，同时介绍子集一子空间模拟的一般方法 定义4 1 q 元有限域g f ( q ) 上的佗维向量空间( g ) 的所有子空间，连同包含关系构成 的格，称为子空间格，记为厶( g ) 当q = 矿为素数，8 为正整数) 时， k ( 鼋) 的k 维子空间的个数 k jq 表示有限域g f ( 口) 上为佗维向量空间 4 1一些二项式系数恒等式的g - 模拟及其组合证明 k ( g ) 是q 元有限域g f ( q ) 上死维向量空间，厶( q ) 是k ( g ) 上的子空间格， 厶( g ) 与布尔格风之间的q 模拟是组合数学的重要研究领域这里所说的g - 模拟是指把布尔 格既上的一些性质和恒等式推广到子空间格厶( g ) 上，在子空间格厶( q ) 上找到它们的 口- 模拟形式，其中q 是参量，当q 一1 时，铲模拟趋向于布尔格既上相应的性质 首先我们引入g a u s s 二项式系数，也称为高斯系数 定理4 1 g a u s s 二项式系数 2 可= 硕万五厂百疋可可 ( 口n 一1 ) ( 口n 一1 1 ) ( q 他一七+ 1 1 ) 2 万= 顼尹t = 面_ _ 面可 翻1 2 而翩 表示礼维向量空间( g ) 的k 维子空间个数其中，m ! = m h 一1 】【1 】；m = q n 1 证明： 下面我们用两种方法来计算( 口) 中k 个有序线性无关组( t ，1 ，v 2 ，v k ) 的个数： ( 1 ) ( g ) 中共有q n 个向量，则v l 有( 矿一1 ) 种取法( 除0 外) ，v 2 不能从口1 张成 的直线上取，有( q n q ) 种取法，v a 不能从u 2 张成的空间中取，则有( q n q 2 ) 种 取法，依次下去，有( 矿一q 知一1 ) 种取法，于是符合条件的( u 1 ，v 2 ，v k ) 的总数为 ( q n 一1 ) ( g n q ) ( q n q n - 1 ) 1 1 ( 2 ) n 为k 维子空间个数，对于每一个k 维子空间有( q 七一1 ) ( 矿一q ) ( q k _ q 凫一1 ) 个有 序线性无关组( m ，眠) ，则y n ( q ) 中k 个有序线性无关组的个数为n ( q 鬼一1 ) ( q k q ) ( q 七一矿o ) 从而 r 一( q n 一1 ) ( g 佗一q ) ( q n q 七一1 ) n 】! 川2 哥= 顼f 习_ _ 骨书2 丽厕。 得证 在g a u s s 二项式系数的基础上，我们得到下列一些重要的一般二项式系数恒等式的 q 模拟，根据g a u s s 二项式系数定义及归纳法我们可以容易证明这些哥恒等式，这里与 前面一样我们只给出它们的组合证明或组合解释 引理4 1 令k ：= ( g ) 为元有限域g f ( q ) 上的礼维线性空间，x 为含z 个元素的向量 空间，z 为含名个元素的向量空间，且z x ，d i m z 仃，则使，( ) nz = o ) 成立的从 v 到x 上的一一线性映射，的个数为 证明： r ( z ，z ) = ( z z ) ( z q z ) ( z q n 一1 z ) 设 v l ，v 2 ，) 为的一组基在，的作用下变为 e 1 ，e 2 ，】，则e t ( i = 1 ，竹) 线性无关不同的序列e t ( t = 1 ，n ) 个数即为，的个数 设 砌1 ，w 2 ，w n ) 为z 的一组基，则由它可扩张成z 个向量因为，( ) n z = o ) ， 所以e l 有( x z ) 种取法由因为e 2 与e 1 线性无关， t t ，1 ，w 2 ，w n ，e l 】可扩张成q z 个 向量，所以e 2 有 一g z ) 种取法类似地直至有扛一q n - 1 z ) 种取法由此可知符合 条件的，的个数即为r ( z ，名) 定理4 2 向二项式定理，在n 维向量空间k ( g ) 上，令 r ( z ，y ) = ( z 一可) ( z q y ) ( z q k - l y ) ， 则 晰一2 薹【别q 晰m 础 其中x y = y x ，z z - - - z x ，y z = z y 证明： 由已知r ( z ，z ) = 0 一z ) ( z q z ) ( z q n - 1 z ) 则由上述引理，p n ( z ，名) 即为从到 x 的满足，( ) nz = o ) 的一一线性映射的个数 为证明该恒等式，换一种计数方式令y 满足z y x ，且d i m ( y ( y ) oy ) = k ， 0 k n ，即y 为k 的一个k 维子空间的像我们可以建立这样的映射；先选出k 的 任意一个k 维子空间矿，将u 映射到y 上，使得s ( u ) nz = ( o ，再将一u 映射到 1 2 大连理工大学硕士学位论文 伍一y ) u o ) 上，取u 的一组基记为v l ，可将它扩充成的一组基记为v l ， 1 ) 1 ，要映射到y 上，且满足f ( u ) n z = o ) 的线性映射的个数为p k ( y ，名) 余下 的基向量则必须映射到伍一y ) u o 上使得，为单射，相应地有r 一惫( y ，名) 种方式又 由定理，q 元有限域g f ( q ) 上礼维向量空间k ( g ) 的k 维子空间个数为，相应地有 豳口尼( y ，名) r 一詹( ，z ) 个，对尼求和即得 卜纠 = 鲋 f k k ( x ，y ) f k ( 妙，z f k ( z ，耖) j 一k ( y ，z 定理4 3 口恒等式4 j j 圈口= g 是恒等式p 2 圳的q 模拟 证明从略，参见k o n v a l i n a 2 0 定理4 4 q 恒等式彳j 2 ：习。 拿 g = = ： 口 芸二习g 是恒等式p 2 缈的g 模拟 证明： 嘲。嘲g 表示所有子空间对( 二名) 的个数，令s = ，b ) ) ，i s i = 习。 匀g 设c 是n = 阻瞻二n + 。，所以，是一个双射故is i = 翻g 司口= i 丁 = 刁g 窿二习。得证 定理4 5 q 恒等式名j s ( q p a s c a l 三角j * 黜g 叫俨k1 口 是恒等式p 2 纠的g 模拟 1 3 证明： x l , x 2 ，x n 是n 维向量空间( g ) 的一组基，k 是k 子空间，分两种情况： ( 1 ) v k 不包含向量z n ，设一l 是。1 ，x 2 ，x n - - 1 张成的空间，k 是一l 的子空 间，而一1 的k 子空间个数为rl 1 i ，设w k 是一1 的克子空间，可1 ，y 2 ，y k 是它的 一组基，将这组基底提升到( g ) 上，给每个y i ，i = 1 ，2 ，k ，加z n 的某个倍数，有g 种方法，则共有q 七种方法 这种情况下子空间y k 的个数为g 七l ，：1 1 l j 厂一 1 1 ( 2 ) 阮包含向量z n ，圪nk 一1 是k 一1 维子空间，从一1 中有l ：一；1 种方法取 k 一1 子空间，再与z 竹张成，就得到( g ) 的一个k 子空间事实上，若y 1 ，y 2 ，y k 一1 是选出的k 一1 子空间的一组基，箩1 ，耽，y k 一1 ，。n 是某一k 子空间的一组基得证 4 2 子集一子空间模拟 k n u t h 1 8 】得到了一个重要的结果，有限域g f ( q ) 上任意两个不同的行梯减形矩阵 ( r r e f ) 对应：n ( q ) 上两个不同的子空间，即：n 维向量空间k ( q ) 的一个k 维子空间a ， 存在唯一的一组有序基( v l ，也，) ，使得矩阵 m ( a 、= 满足： ( 1 ) 仇，( i = 1 ，2 ，k ) 的第一个非零值是1 ， ( 2 ) v i + l 的第一个非零值出现在仇的第一个非零值右侧， ( 3 ) 在含v i 的第一个非零值1 的列中，除l 外其它元素全为零 令f ( a ) = _ 0 1 ，a 2 ，n 七】为 1 ，n 的子集，其中a l 为m ( a ) 的第i 行中第一个非零值 所在的列，则，是从子空间格厶( g ) 到布尔格既( q ) 的一个秩保序映射 例4 1 如果f ( a ) = 1 ，3 ，4 ，6 ) 岛，则m ( a ) 有形式 其中掌为g f ( q 1 上的任意值 1 木 o 0 o 0 o 0 0 o 1o o1 o o 1 4 睾 掌 丰 o o o 1 幸 木 幸 o 大连理工大学硕士学位论文 事实上，如果给定一个集合s = 0 1 ，a 2 ，a k ，则有类满足上面三条性质的行梯减 形矩阵m ( a ) 与s 对应，九表示在m ( a ) 中第i 行的车的个数，计算可得= 佗一a i - k + i ， 矩阵m ( a ) 中所有奉的个数t ( s ) = 冬1 九，则与集合s = n 1 ，a 2 ，o 七) 对应的所有行 梯减形矩阵的个数为q t ( 鳓也就是说，对于任意一个k 元子集s = 口1 ，a 2 ，a 七) ，有 q t ( s ) 个子空间与之对应 在k n u t h 的基础之上，王军j 又得到了下面的结果，这对子集子空间模拟提供了 更好的方法 定理4 6 设p 是玩的一个性质，既【纠是玩中满足性质p 的所有子集，则在子空间 格上有性质p ( g ) ，使得a n ( g ) 满足性质p ( g ) 当且仅当f ( a ) 满足性质p 推论4 1 厶( g ) 【纠是( g ) 中满足性质p ( g ) 的所有子空间，则有如下一对恒等式 玩圳= 1 s b h 【纠 l n ( q ) m i = q t ( 研 s e b p ( 4 2 1 ) ( 4 2 2 ) 显然，在上面推论中，当g 一1 时，口- 恒等式4 2 2 趋于恒等式4 2 1 对于前面提到的所有木的个数t ( s ) ，接下来给出它的另外表示及相关的两个定理 对于任意一个( 0 ，1 ) 序列w = w l w 2 ，定义 t i 一1 i n 口( 叫) = 挑( 丽+ + 可习， i = l 其中研= 1 一w l