（基础数学专业论文）向量空间上恒等式的q模拟及组合证明.pdf

大连理工大学硕士学位论文 摘要 k ( 口) 是q 元有限域g f ( q ) 上的佗维向量空间，厶( 口) 是由( g ) 的所有子空间构成 的子空间格，既是n 元集合 1 ，2 ，n ) 的所有子集组成的布尔格布尔格与子空 间格厶( g ) 之间的哥模拟指的是把布尔格上的一些性质和恒等式推广到子空间格上，并 在向量空间上找到它们的酽模拟形式，其中q 是参量，当q 一1 时，哥模拟趋向于布尔 格上相应的性质 此外，恒等式的组合证明或组合解释赋予了恒等式一定的计数意义，组合证明最常 用的方法是分别用两种不同的方法对恒等式的两端进行计数，一般通过构造两个集合之 间的双射，这两个集合的个数分别表示恒等式的两端，从而根据双射的一一对应性证明 恒等式本文也正是采用了这种方法对恒等式进行组合证明，从而揭示组合证明的一般 方法 本文给出了一些重要的二项式系数恒等式的组合证明或组合解释，并从向量空间角 度给出了一些恒等式的哥模拟及组合证明，其中突出的成果是给出了立方和恒等式的一 个新的于模拟及组合证明 文章主要内容可概括如下； 1 介绍了一些与向量空间上恒等式的争模拟有关的基本知识和基本概念，如：偏序集， 格，组合证明，二项式系数等 2 给出了一般布尔格上一些重要的恒等式及其组合证明或组合解释 3 引入叮模拟的概念，在向量空间上给出了一些重要恒等式的于模拟及组合证明，并 介绍了子集一子空间模拟的重要方法及多重集上的m a h o n i a ns t a t i s t i c 4 从向量空间出发给出了恒等式k 。k a = r 孝1 ) 2 的一个q - 模拟及组合证明 关键词：组合恒等式，布尔格，子空间格，争模拟。组合证明 型堂至! 堕量窒囹占堕要塞笪生堡塑垦塑盒亚塑 q - a n a l o g u ea n dc 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 so n t h ev e c t o rs p a c e a b s t r a c t l e tk ( 口) b ean - d l 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 ef i e l dg f ( q ) w i t hge l e m e n t s ，厶( q ) i t sl a t t i c eo fs u b s p a c e s ，a n d t 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 ，n ) 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 i lt h eb o o l e a n l a t t i c ea r ee x t e n d e do n t ot h es u b s p a c e - l a t t i c e t h e nt h e i rq - a n a l o g u ea r ed i s c o v e r e do nt h e s u b s p a c e - l a t t i c e ，w h e r eqi s a np a r a m e t e r w h i l et a k i n gt h el i m i tq - 1 ，t h eq - a n a l o g u e s b 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 i lt h eb o o l e a nl a t t i c e m o r e o v e r ，b yt h ec o m b i n a t o r i a lp r o o f o rc o m b i n a t o r i a li n t e r p r e t a t i o n ，t h ei d e n t i t yi se q u i p p e d w i t hc e r t a i nc o u n tm e a n i n g t h em o s tg 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 o s i d e so ft h ei d e n t i t yb yt w od i f f e r e n tm e t h o d s g e n e r a l y , t h r o u g hm l d i n gab i j e c t i o nf r o m o i l es e tt oa n o t h e ro n e ，t h en u m b e ro ft 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 e i d e n t i t y b e c a u s eo ft h e1 - 1p 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 s t h i sm e t h o dt og i v ei d e n t i t i e st h e i rc o m b i n a t o r i a lp r o o f a sar e s u l t ，ag e n e r a la p p r o a c ht o c o m b i n a t o r i a lp r o o fi si l l u s t r a t e d i nt h et h e s i ss o m ev i t a li d e n t i t i e sw i t hb l n o m l 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 o 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 es u b s p a c e - l a t t i c e 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 ta n e wq - a n a l o g u eo ft h e c l l b e - s u t d 目i d e n t i t yi so 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 fo v e rt 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 d f o l l o w s ： 1 i n t r o d u c er e l e v a n tb a s i ck n o w l e d g ea n dc o n c e p ta b o u tt h eq - a n a l o g u eo nt h ev e c t o rs p a c e ， s u c ha sp o s e r ，l a t t i c e ，c o m b i n a t o r i a lp r o o f , b i n o m i a lc o e f f i c i e n ta n ds oo n 2 s o m ei m p o r t a n ti 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 rc o m b i n a t o r i a li n - t e r p r e t a t i o no i lt h eb o o l el a t t i c e k 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 ei m p o r t a n ti d e n t i t i e sa r eg i v e n w i t ht h e i rc o 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 ra ni m p o r t a n tm e t h o do f s 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 o nt h ev e c t o rs p a c ean e wq - a n a l o g u eo f t h e i d e n t i t y ：= l 舻= ( “孝1 ) 。i so b t a i n e dw i t hi t s c o m b i n a t o r i a lp r o o f k e yw o r d s ： c o m b i n a t o r i a li d e n t i t y , b o o l el a t t i c e ，s u b s p a c e - l a t t i c e ，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 独锈魏说弱 作者郑重声明；本硕士学僚论文是我个人在导师指龆下进行的研究工作及取得研究 成聚尽我所知，除了文中特嬲加以标注和致谢的地方外，论文中不识岔其他人已缀发 表袋撰写簿硬究蔽采，逮不惫禽为获褥大遂疆王夭学凌莛德擎位静学豫凌 菱警瑟爱藤过 的材料 作者签名；钕整率日潮；逸丛! ! 盖丘 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解”大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 作者签名： 导师签名； 赵垫辱 黝p 大连理工必学硬士学位谂史 1 善| 害 李疆究瀑蝴戆研究方囊是组合数学组舍数学，叉黎努离散数学，毽蠢时逸把 缀合数学衣霞沦由日在一起稚菇离散数学，它是计算机穗现戳后迅速发展越来毂一门数学 分支，计算机科学是算法的科学，计算机所处理的对象是离散的数据，而研究离散数据 的科学恰恰就是组合数学组合数学不仅在计算机科学中有重要的应用，而且猩企业管 攥，交逶规麓，金聚分费等镁壤罄骞重瑟黪应曩馀基，缎台羲学黪方法，晷想黧撰垄蓑 术已经逐渐渗遴懿了各个学辩领域。组会数学研究静镁域有很多，魏；计数组会学，代 数组合学，图论及其算法，缀合优化，缀合设计，恒等式的q 模拟及其组合证明簿等 本课题所属的研究领域是恒等式的口模拟及其组龠证明，它对于组合数学的研究有 葛鬻重要熬黎义，赋予了燧等式一定懿谤数意义，秀囊爱数学嚣务学势囊识与缀套数学 有机遗结合农起，一壹以采都深受组合学家们的譬褫 g o l d m a n 和r o t a 2 4 1 于1 9 7 0 年开始对予空间格和元集上的带尔格之间模拟做系统 性地研究，他们给出了一些铲恒等式饺子空间格上的缀合解释，并说明当g 一1 时就是 一簸懿二瑗式蕊数霍等式。糙蛾矗斓予1 9 7 1 年缮爨g 嚣有疆壤上懿珏维良量察瓣戆基 筒个j 维予缀闯都有唯一的一组满足一定条件酶有枣基以后m i l n e 4 0 于1 9 8 1 年给 出了一些从予擞间格到n 辩榘上的布尔格的保序映射之后王军【5 于1 9 9 9 年擞保序映 射黪基础上搀旋了从子空阉捺的某一商捞舔l 布尔格的格映射，这对憾等式的窖- 模拟和子 蕊一予奎戆摸羧产生了缓大瓣贾藏，疆霪，冯红喇叉怒宅搀广蘩多蘩集上。1 9 9 2 年， y g c h e n 和r o t a 1 4 1 还给出了包含排除藤邂在子空闻格上的p 模拟 g a r r e t t 和h u m m e l 2 0 予2 0 0 4 年从分拆的角度给鼢了二项式系数恒等式恐1 3 = ( ”善1 ) 。的个争模拟及窖模拟的组合证嘴，之后珊鼢挑材叫又给出丁它的个黧筒单的 争模援黟式。瓣年，s c h l o s s e r 黯) 鼗t 攘广，嚣霆q - 缀数给凄了e 函护，m = l ，2 ，3 ，4 ，5 的q _ 模拟形式但是还没有义章从向量空间的角度给嬲它的于模拟，所以对于逡炭恒等 斌在向量空间上的哥模拟掇研究的个新思路 大连域蔗大学硕士学位论文 2 绪论 本文烹获扶龛量空翘建发给出了一些毽等式鲍q 模拟及其缀会证骧，首先我弼奔绍 一些与之耀荧酶基本翔谈裾基本褫念。 2 1 偏序巢 偏穿枭蹙一稀特定瓣察，它是樊生要嚣彦关豢集。吴雾遮滋，集合e 涟淹其主邃 偏序冗构成地关系集( e ，娜，般记为p = ( e ，) ，所谓偏序( 或序奖系) 是一擞具有自反 性，反对称性和传递性地：元关系，例如，数之间地不大于关系，自然数之间地整除关 系，集合之怒遮包食关累镣把寨台e 戆基数嚣为馕痔集p 翦黔，跨为有隈缀熬镶序集 称为有限壤謦集。磊在p 上，对手经慧元素罨瓠酝闽沁捌垮隽有限偏枣集崤，称p 鸯 局部有限偏序集这两类偏序集是组合理论中的奎簧研究对象偏序集上所有链的长度 的最小上界竣上确界，称为偏序集的长度，记为z ( 聊 骟彦集戆最大元，栽小元； 偏序嶷p = ( e ，s ) 酶子集s 中的笼索岛若在s 中不存在其它元素为使褥8 嬲 称a 为s 上的极大元对称地，若在8 中不存在其它元素z ，使得z 墨a ，则称n 为s 上 的极小元若取s = 刀，则分剐称。为偏序集p 的极大元，n 为偏序集p 的檄小元当 尹秀毒疆壤警察时，箕极太元，毂夺嚣慧是毒在鹣，若对予p 戆爨有元素墨坶有。a ， 谢称8 为俺序集p 静最大元对称绣，著对于p 鹣所有元素。均有a s 氟黄g 称a 鸯偏 序集p 的最小元偏序熊并不总有最火元，最小元若它时有限金序集，则宦总有最大 元和最小张 2 2 格 格是类代数结构它是建立在偏序集p = ( e ，蔓) 之上的，由昱的任意游豢毛y 构 造兹蘩下嚣令集会1 ( 茗，坊= 扛e | 茹毛y s2 及地每，墅) m 扛e ；s 霉，：s 爹 它们作为p 的子集均为编序集，般不一定有最大浠或最夺元游对p 的任慧元素为y ， 1 ( z ，y ) 均有最小元，2 ( ，y ) 均有最火元，则称f 为格，并记为 在格c 上，把1 0 ，y ) 和其最小元的对应关系视为一类二元避算，称为。和y 的交， 记秀。 y 瓣黎蘧，怒弼轴，药窝冀最大元懿翼 应荧系褪为。爨y 鹭缕，记必茹v y 。它 们是格上撼最基本的运算这两类运算满足； ( 1 ) 同律霉v 霉篇；z a z = 霉 ( 2 ) 垄蹬熟律# v y = y v x ；x a y = 譬 z 3 整卷垩：塞璧茎塑尘篓堇茎鳖釜壅鍪墨堡垒堡鏊 ( 3 ) 缀合律茁v ( y v z ) = ( i c v 辨v z ；嚣a ( y a # ) = 囊a y ) a z 。 ( 4 ) 暇牧律x a 和v y ) = z v 和a y ) = $ ，其中茹，y 和# 均为e 的任意觅索，因此格又 可视为满足上述嫂条规律的代数结梅c = ( e ，v ， ) 虽然格的理论建立较晚，大约在2 0 谶纪颦代左右，僵是徽快就在解决亭集闻题和缀合闻糕及代数闲题中迅速发展，成为 有关研究的有效理论基础与一般具有序特征的代数结构不同的鼹，格中元素的序特征 苓是羚袁瓣，委愚蠹在懿。这是鑫手它露鹣旁关系完全瑟l ：盂等爨壤又捂趣海在逶箨来蘩 衡：z 簟当且仪当z v y = 或者$ s 掣当且仅当x a y = z 这也反映了格地交遥算和结 熬算地对称性。有些重要盼撂的傩子。例如，昱一( 2 e ，) 是格，逸里2 e 势e 戆骚考子 集的构成的集族，而l e l n ，其上的结遥簿z v y 为集。和集f 的并集，交运算茹a y 为 黎。和枭口的交枭又如，若自然散n 的所有正整除数缀成集合殿，e 的觉索z ，y 有序关 系茹两鹭疆佼当茹能整徐弘癸| 德窿集为p = ( e ，r ) 捂，茹v y 为嚣帮静最小公倍数， 嚣a 口为茹和y 的煨大公约数 2 3 映射及组含证明 设y ( 麓) 皴n m 为m 鹫n i 臻陕彦争，懿集会t 黯予每伞$ m ，淹过，麓对应 到嚣的象n ，记为! ，m ，0 ) 我们通常写，：m 一来代替f 了( ) ，当m 和 有限黪，mt lml ，n ；lnl ，我弱以绘掰戆元豢缝号，浚m = 茹l ，托，霉桃 ， 最然，给一个，虢等价予给一个的m 个元素的表，比方说， ”l ，抛，) ，像们依 慕一顺序，允许璧复地列斑那么所谓绘出这个袭就意味着皱是筑( 1 曼ism ) 的象； 职一，诹) 换句话说，给个，就等价予给出一个属于n m 的m 元缀，也称为一个一 选择这榉，就找到了把7 ( 尬) 记为n m 的理由。 弓l 理2 1 有限个宥限集合的乘积案合的元素个数满足： ”im | 狐越l = 疆l 越| _ | 豫l | 憋| - t | 裱| t 黼it 舞1 迸孵： 事实士，静元组曲1 ，讹，) 的个数等予1 中笋1 的可髓选择数 li 乘以2 中! j 2 的可熊选择数l 2l ，等等，乘以中y m 的可能选择数lm 。1 ( 因为这些选择是 穰互独立鹣) 由这个引理容易证得下面这个定理 定壤2 。1 艇到娉睫象令敷毒下式给出； 了( 矗蕺) = l n m | _ l n l i 吖i 对每一个子集a c m ，我们表示 歹沦) ：= ，和) | 嚣譬 这榉就定义了一个从b ( m ) 列b ( ) 内的映射，称为，到m 的子枭集合上的扩张这也 曩，表示其孛嚣( 掰x 君) 分舅g 表示m ，n 懿搿宥子集梅凌懿集会。 4 大连理i 大学硕士学位论文 对所有y n ，m 的子集 i - 1 ( ) ：= z l ，( z ) = ) 可以是空的，称为由，得到的y 的原象或逆象 定理2 2 m 的子集个数，包括空集，由下式给出： 8 ( m ) = 2 1 m i 证明： 设是具有两个元素0 和1 的集合，我们把子集acm 等同于由z a ，( z ) = 1 ， 否则，( z ) = 0 所定义的从m 到的映射，( 通常称为特征函数) ，这样，就建立了集合 b ( m ) 到n m 的一个一对应，其中n = o ，1 ) ，因此b ( m ) 与n m 有相同的元素个数 i n l i m i = 2 i m i 得证 下面我们介绍什么是组合证明，首先，我们回忆一下代数学中的知识， ( 1 ) 如果两个不同元素的象也不同；x l t 2 = 辛，( 茹1 ) ，( 茁2 ) ，n m 就称为是单 射的( 或叫做一个单射) ； ( 2 ) 如果的每个元素都是m 中某元素的象： 了z m ，使得，( g ) = y ， 就称为满射的( 或叫做一个满射) ； ( 3 ) 如果，既是单射的又是满射的，就称为双射的( 或叫做一个双射) 在( 3 ) 这种情况下，的逆或反，记为，定义y = ，q ( 。) 当且仅当z = f l u ) ，这里 m y n 要数个有限集合e ，换句话说，确定其大小，原则上就是建立e 到另个元素个 数已知的集合f 上的双射；从而1ei = ifi ，这也就是计数问题中所谓的组合证明 下面举个组合证明的简单例子， 例设e 为的所有偶数个元素的子集的集合，f 为其余子集( 具有奇数个元素) 的集合，我们可选择z n ，建立如下的e 到f 的双射根据z 不属于a 或。a ， i c a ) = a u 扛) 或a - 和) ，因此，lei ifi = 1ib ( ) | - 2 ”1 2 4 排列，置换，二项式系数 对于每个不小于1 的整数k ，我们记： 嗍_ l ，2 ，耐 定义2 1 集合的一个七一排列。( 1 七n = in 】) 就是一个从到的单映射n ，我 们用u k ( n ) 来表示的k 一排列的集合 因此，给出这样个a ，首先等价于给出的k 个元素的子集 b = 8 ( 吲) = o ( 1 ) ，o ( 2 ) ，n ( ) ) 其次，等价于给出了b 的元素个从1 珂的编号， 最后，等价于给出了的个元素的全部排序的子集，也经常叫做的个“排 列 5 整娄兰! 旦量至塑土壁箜塞堕望：堡塑墨堡垒堡塑 崴理2 3 n 的一排列个数( 1 墨奄s 扎= fnf ) 等于 魄c g ) i 一( 孔k = 他( 礼一1 ) ( 忡一+ 1 ) 。 诞瞬= 辘然，l 圈) 豹象。( 1 ) 鸯嚣秽霹麓选择；。1 ) 选建后，困必n 是尊慰的，8 ( 2 ) 口( 1 天 n 国裁只寿余下蛉积一1 ) 申可能；类似她，疆为n ( 3 ) 口( 2 ) ，接( 3 ) a ( 1 ) ，对a ( 3 ) 只有 m 一2 ) 种可憝地选择，等等；最尉，对o ，恰有余下一4 - 1 ) 种可能的选择 因此。a 的个数等于所有这夔选择数的乘积，即等于 摊国一1 ) ( 髂一2 ) 国蠢+ 1 ) 注；如果奄 耐k = 0 定义2 2 案龠爵鬟换髓是翻鸯身稚双箭，我镯壤g ( 辩表示酶显换榘套 定理2 。4 。( n 净1 ) 姆黧换令袭等千癌。 诞骥； 仿照上面定理的涯法易碍证 寇理2 5 用b ( n ) 来表示的子集的粜合，的予集个数用( ：) 来表示，则 = 1 s ( n ) 降警一生业掣 = 醋= 奄)2 蕊i 霹2b 奄， 诞鳍； 蓍先涯爨等式国= l 嚣( 秘净肄，其它豇令都是它兹囊接推论，热果是一0 ，魁 警。1 。虫予| 嚣( ) 只会n 鲍整予集，从掰l 嚣( ) | = 1 假设1 ，每个排列n e u k ( n ) ，对应着b = i ( a ) = 。( 1 ) ，吐( 2 ) ，a ( ) ) l 魄( ) l ，剡 ，是u k ( n ) 到z 3 k ( n ) 的映射，使得对所有b 玩( ) ，有 ，一1 ( 暑) | - 烈 西为b 有翮种可能前编号现在当b 跑避取( ) 时，互不裙变的原象集合i - 1 ( 嚣) 完全 覆盖了狐( ) 爵藏，醯( ) 酶元素个数等予瑟裔li - 1 ( 嚣) l 静稀，这里b 繇( ) ，邵 裔； 国b = l 壤( ) | 一l ，“( 鳓 一圳段( 明l 嚣 因此，壤( ) j 一镣得证 庭义2 3 整裁叫做二项式系数 8 大浚理工大学硕士学位论文 3 子橥格上一整誊要蠹白恒等式 上一濑，我| 了已爨大概分缀了盼么罴组合添赣，及缝合诿髓懿懑慧，努法，并弓l 入 了二习l 式蓉数国，速一章将绘窭一毯美予二磺式蓉数瓣重要援筹筑及它髓黪组会涯霹， 通过这憋侧予将使我们进一步理解缀合诫明的恩怨和方法 3 。1 密尔格及子集鞲 布尔格是一种特殊的格，它是姆布尔代数b 一( 2 e ；u ，n ) 同构的格，布尔格的结运算 鼗交运棼分别澄痊予零象代数戆黉媾算秘突运葵 这量螃蹴的帮尔代数，是布承( b o o l e ，g 。) 予1 8 4 7 年及1 8 5 4 每研宄恩维规撵逻辑 学，数璃逻辑) 是提出的，掰它作为一种特殊的格受g 怒戴德金( d e d e k i n d ，j w r ) 后来掇 出的，所湛布尔代数，是指个有序的四无组； ，v ，) 其中b 是非空集念， 和v 分 掰是b 纛酶二多运算，嚣“是宠义燕羔雏伞一手巷运算，势藏游嫠下舞条箨：辩手矮 意8 ，敬c b ( 1 ) a b mb a a ；a vb 一6 v m ，a ( b 磅= 弘a 妨 q 矗v 转vc ) 黜( 8 v v c ( 3 ) 。# 如、，6 ) = 螂口v 国 妨= m 辫，( 球 砩v p c ) v ( c a 弯= 国v 婶a b v 本a ( e v 癌) 。 ( 5 ) a ) vb ；峨 v n ，) b 一乱 1 9 0 4 年，掌廷稷h u n t i n g t o n ，e v 。) 发浚：著鬃合a 骞令= 嚣逛算v 秘令一：惑藿 算，定义口 6 = v ) ，势满足； ( 1 ) n vb = b v 弼 ( 2 ) 。如 v 缸 6 ，) = a ； ( 3 ) ，8 v vc ) = 缸v 6 ) v c ； 蠢a 爨豢象健数。逸惫枣尔我数耱令典型臻桊，1 9 6 每，1 9 6 8 攀戈莱滚( o r a 抛r ，g 。) 和莫肯济( m c k e n z i e ，r n ) ，塔尔斯慕( t a r a k i ，a ) 分别独娩地进一步发现布尔代数可仅用一 个恒等或寒定义 定义3 i ，2 蝴为珏元豢舍 i ，2 ，牲 戆鹭有挚栗跨成嚣慕族，按照包舍荧拳“至”， b = ( 2 m ，) 燕子集格，简记为置，其上的结运算。v ! ，为集茹和凝可的并集，囊运算 嚣a y 秀慕嚣和襄箩的吏栗。 7 整堂蓬：堕量窒塑主题簦苎塑堡燮憋墨垄鱼至翌 3 2 一些霍妥瓣= 硬式系数瞧等式及组仑涯现 般二硕试聚毅 = 巫等铲一赢， 扭z 脚 可以表示n ：元数集 l ，2 ，讹 的血子寨的个数。关予般二项式系数霞) 有一黧黧要的 憾等式如下： 注：这些憾等式根据二硬式系数的定义及归纳法研容易证明，这里只给出它们的组 会涯饔或组会熬棼 下面的诚稿中。甩袭示集合 l ，2 ，扎 寇理3 1 仁嘲式定理， 谩x y = 粥砷于毒一整数站馥我爨孝： ( 卅扩2 薹g ) 南” = 矿+ ( ：) x n - l y + ( 易妒以护+ + g 二，) 嚣尹1 + 矿 诞明t 首先考查下列展开式系数o k ，j ：p + p = a 马魏= 1 茹o ，其中最= 窜+ ”， 瓣，凌是邋过选择n 令嚣子最箨瓣) 孛戆蠹个，热盎个嚣予巾戆”硬黎以余下 女) 个匿予中的“旷珊i 得蓟的，所以f _ n 一_ j 。圆诧系数瓯1 一敛。，等予在他个 因子中选出个不同因子懿的选择数为( ：) 即原式成妲得证 倒1 ：如果聋= f = 1 ，那么銎；o 娌) 一2 ”，因此 1 ，2 ，n 的予熊总数为2 “ 键2 ：热聚# = 一l ，y = 1 ，零么2 卸( - - 1 ) 2 国= 0 ，获麓话说，舞会 l ，2 ，砖懿媛 ”乎集与奇”子集一样多 宠理3 2 恒等式童2 j 鹪。f ，n 、 惫，n 一詹， 诞明： ( 表忝“觉集会翻懿爨骞毒元子集随个数，( 0 蠹) 表示耪有n - k 元子集瓣令数， 设店是任个奄瓣集，掰a 关子集合潮的补集a 鼹铭一奄j 抒煞职每一个膏元 予集对应一个竹元子集反过来，每一个n 一豇元子集也对应一个元子集，所以m 盼所有七元予襞与所有礼一元子集存在一对应关系，从而q ) = ( 。! ) 宛蓬3 3 。恒等式曼墓霪 g ) ( ：) 一g 二 ) 8 大连邋正大学硕士学位论文 证蘸； 设a 嫩他元集合i n 的个元子集，b c a 魑a 的个z 元子集，则谑) ( ) 表示 所有集合对( a 司的个数，令s = ( a b ) ，isi 一( ：) 渤设c 是n 元集合的个2 多毫子集，b 筵 n l c 懿一个蠢一1 嚣乎集，令t 一 如固 ，l r l 一 ( 器) ， 下面惫立s 与? 之阉翡个映射，：( a ，b ) 一( b ，a b ) ，煲| 递浃射，。：( q d ) 一 ( g + d ，g ) ，所以，是个双射故isi = ( ) = iti = g ) 以二：) 得证 定理3 , 4 。憾等式曼未，( p = c d - 三角， g ) = g 二弘c ；1 ) 涯骧； ( 表承n 元集台两豹所有皋嚣予集静个数，努薄释情鬣t ( 1 ) 冠子集包含竹，取t 1 ，2 ，竹一1 ) 中任一奄一1 子集b ，酋t o ) 是m 的膏子 集，共有( n - 1 1 ) 个 ( 2 ) 。凳子集不寇会这霹裴 l ，2 ，牡一l ，瓣令蠢子豢，邀是两戆凳子集， 共有( 1 ) 所以，( 一( i ) + r 神。得证 定理3 5 憔等式8 2 4 ( v a n d e r m o n d e ，恒等式， e ：5 ) = 虱三；) 诞明t 霾髓翔_ 遴a + b 元嶷会伽l ，n 2 ，m l ，粥2 ，硒 匏珏警桊懿个数鸯( 8 圆，褒在 卷 们用另一种方法来计算它的m 子熊的个数，先从- 1 ，铆，) 选n i 个元素，有 ( 0 i ) 种方法，然后从 m i ，m 2 - 一，孤) 申选余下的个，有( b 种方法，对i = 0 ，l ，2 ， 求秘得裂跏子集个数为乏涤。0 ，蔽此 戏立褥诞 p ：一妻i = 0g 叫6 ) 大谶理工大学硕士学位论文 旗子空闻格上的铲模拟 逶避蒋嚣瓣章节，鼗稍琶经黠毽等式静经会迸浚有了令深入翡了解，势戆蒸本掌援 缀会诞聩螅方法，这一章将主要讨论子交越楂上憾等式驰争摸擞及其它们搬向爨空间上 的组合溅明，同时介绍子集一子空简模拟的个穷法 定义4 1 q 笕有限域g f ( q ) 上的竹维向量空间碥q ) 的所有予誊闾，连同恕含荧系构成 始格，称海予登阀貉，记为。( 葑。 当一f ( p 秀素数，s 秀王熬霾斡融， k 国) 的维乎空间的个数 4 + l 一缝墓爨恒等戏鹣q - 模拟及缀含漩明 嬲。表嚣骞限域8 掌( 鼋) 上为嚣维囊量空瓣 ( 曲是口元有限域g f ( q ) 上他维向量空间，岛( 口) 是k ( g ) 土的子察间格，c 。( q ) 譬帮承梅魏之闺懿模熬壹燕熬套数学砑囊黪整妥镁域，g o l d m a n 程黎聪氇籀次徽 丁系统憷豹礤宠。这服所说的铲模掇是对g 趋透1 鹣讨论，鼷：当g - 趋近乎l 对，子奎 阉格上酌螫性质福波蟪变为布尔格上瀚往质。 首先我们引入g a u s s ：顷式系数 定理4 。1 湖貔脚二磺式系数 翻。= ( 矿一1 ) ( 矿一种国”一口2 1 ) ( 驴1 ) ( 驴一g ) ( 矿一g 一1 ) 舻一1 ) 矿一1 ) ( 矿一轴1 一1 ) ( q * 一1 ) ( g o l 一1 ) ( 知一1 ) 嘲 研丽 表示器缭向薰誊闻礁锄的舞维予蜜闽个数。葵中，潲l = 黼秘一霹f l 】：潲一酽一1 证嚷： 下戮我托耀嚣种方法寒计算碥( 莉巾k 个有廖线性无关级l ，搬，。，冁) 的个数； ( 1 ) 。k 秘中共霄矿个向量，鲻啦有( 矿一1 ) 种取法( 除0 争辩，现不麓扶瓠张戏 装壹线羔取。骞g ) 黪驭法，魄苓爨跌键，哦袋凌戆空麓审墩，裂蠢( 矿一扔耪 取法，依次下去，啦有一矿“) 种取法，于是符合条件附慨，t 1 2 ，) 的总数为 ( 矿一1 ) ( 矿一妨- ( 矿矿以) 。 1 1 整巍墨! 随茎窒堂点堡篓壅塑暨趔堡垒盒鋈篓 ( 2 ) n 为k 缝子空鬻个数，瓣子每个k 缝子空鬻骞f q 2 一1 ) ( 矿一q ) 岔一斋_ 1 ) 伞有 序线性无美缀( w 1 ；w 2 ，氓) ，则k 妇) 孛k 个有窿线性笼关组鳓个数为( g 捂一1 ) 渺一 q ) ( q i 一口扣1 ) 从面 = 窨器哥描一赫。 襻诫 在g a u s s = 璞式系数魏摹懿上，我 j 褥麴下裂一些蘩簧熬一般= 矮式系数攥等式戆 g 摸拟，根据g a u s s 二埂淀系数定义及朔纳法我们可以容易证明这些q - 恒等式，这胆与 前瑟一祥爵 们其绦出它僻静缀合证露竣缀会解释。 葶l 臻4 1 。令磙滞磙( 峦建元蠢藩城g f 汹 姆维嫒缓登竭，并舞会鬈令觅索的惫量 空阀，z 为合g 个元素姆向熏蜜趣，鼠z x ，妇矗茗 弼刺使，( 娃) n z = o 成立的扶 矿潮x 上的一一线性映射，的个数为 玩江，z ) = 秘一# ) 墨一q z ) 露一矿_ 1 蠢 程秘； 设 ”l ，抛， 为k 的一组基禚，的作用下凌为 e l ，e - 2 ，e 。) ，则氐0 1 ，n ) 线骥无关。苓鬻豹痔嗣嚷8 = 1 ，珏) 令数攀秀歹瓣个数 设 蛾，她，堍 势z 的一组基，奥l 出它可扩张成z 个向量。匿秀，( 磙) n z 一 o ， 掺黼e l 有2 ) 稀取法由戳为e 2 霹e l 缭往无关， 钟l ， w 2 ，斑 可扩张成q z 个 向爨，所以睨有扛一q z ) 种取法类似地直至有0 矿- 1 9 ) 种取法由此盯知符合 条彳譬酶，瓣个数鼙秀最溆砖 定壤4 2 。* 二磺式定i 移在体维向素蜜蕊磙( g ) 点，令 段( 黾# ) = 和一国和一g 国一“1 f ) ， 刘 脚。磊阴。踯如 英中x y 2 y x ，茁z z ，y z z y 逶骥t 由已知瑞( 霉，。) = 一2 ) - q z ) 一q n - 1 z ) 鲥由上述引理，瑞( 就= ) 即为从k 到 x 豹凑是，( 磙) 爨茗= 固熬一一绫瞧浚麓盼令数。 为证孵激慑等式，换种计数方式令y 濂熙茹篓y x ，蓝d i m ( ，( 坛) n y ) 一k ， 0 k s 吼郄y 为磙静令k 维子空辩静像。我翻鼙璐建立这榉酶浚射t 竞选出k 静 任意一个k 维予空间u ，将u 映射到y 上，使得f ( u ) nz = o ，荐将碥一玎映射到 大连联麓大学硕士学蚀论文 曜一y ) o 嬉上，袭u 夔缝基 琶势镪，镪，虿将宪扩充纛磙懿一组萋记蠢锻，强。 砚，嘞鬻映射到y 上，且满足( u ) n z = o ) 的一一线性映射的个数为最( 玑g ) 余下 的基向量则必须映射到( x y ) u o ) 上使得，为单射，相应地有r 一( ”，z ) 种方式又 由定理，q 嚣弯限域g f ( q ) 上n 维南避空阕( 鼋) 的维子空越个数为l ： ，糖应地有 嘲。最z ) 张山：) 个，对求和鄢得 她加砉翻。勰扭，苟 ；耋酗帆) 是恒等式勰2 0 砖窑壤毒软。 证明t l ：l 。裘永椎维蠢量窳麓弦潜秘掰有是维予缀霞懿个数， 髓三蟊l 表示掰考n 一奄 维子空间的个数，若a 怒n 维向量空间k ( g ) 的个维子空间，a 是它的补子空间， 劂a 是( 口) 的个n 一维子空间反过来，若b 是n 维向案窘间k ( 口) 的个n 一七 维子空霾，爨占是磙( 莉懿今垂线予空蘑，瑟戳簿令毫子垒鬻黠应令摊一是子空 间，故| ：| 。l “。| 襻证 定理4 4 。一恒等式4 1 学 【刭。【铆。2 【列。【：二l 。 建恒等式馥襄菇酶q 摸拟 证明t 设a 燎作维向量空间磙( g ) 的一个维子空间，茸ca 悬a 的一个z 乎空间，则 嘲。| ：| 。裘零瑟套子空瓣辩浮，司戆个数，令s a 翻 ，l sl lj 2 高。囝。设g 是n l a j 口ol 挥dl 8 维向量童阍k ( 虫的个f 维子空间b 是k c 的一个一；缎子空间，令t 一“c ，d ) ， = 团lq 卜k - 一1 3 。 ”“ 目 、-：叫 n 一 ，m = 尊 m jf 式等恒 铲 瓢垂理定 一一 整垄兰! 鱼兰窒塑圭坚兰查塑垡：垄垫垦垫全兰塑 下面建立s 与t 之间的一个映射， ( c + d ，g ) ，所以，是一个双射故isl = 定理4 5 g 一恒等式# o 由p a s c a l 三角j ”窿 是恒等式p 2 剀的g 模拟 证明： 。2 一，z n 是n 维向量空间碥( g ) 的一组基，垓是子空间，分两种情况： ( 1 ) k 不包含向量。n ，设弘一1 晕x l ，x 2 ，。一l 张成的空间，是k 一。的子空 间，而k 一1 的k 子空间个数为l “：1 i ，设w k 是k l 的子空间，y l ，船，y k 是它的 一组基，将这组基底提升到k ( g ) 上，给每个y i ，i = l ，2 ，加。的某个倍数，有g 种方法，则共有驴种方法 r 1 1 这种情况下子空间的个数为矿_ 1 f l 尤 j ( 2 ) ，k 包含向量。，n k i 是k 一1 维子空间，从k 一1 中有| ：一1 种方法取 r 一1 子空间，再与茹n 张成，就得到( g ) 的一个子空间事实上，若9 1 ，9 2 ，玑一l 是选出的女一i 子空间的一组基，y l ，y 2 一，y k - l , z 。是某一子空间的一组基得证 4 2 子集子空间模拟 k n u t h f 3 3 j 得到了一个重要的结果，有限域o f ( q ) 上任意两个不同的行梯减形矩阵 ( r r e f ) 对应c n ( g ) 上两个不同的子空间，即： n 维向量空间v n ( q ) 的一个k 维子空间a ， 存在唯一的一组有序基( 钆v 2 ，u 。) ，使得矩阵 m ( a ) = u 1 v 2 ： u 满足： ( 1 ) ，( i = l ，2 ，) 的第一个非零值是l ， ( 2 ) _ v i + l 的第一个非零值出现在的第一个非零值右侧， ( 3 ) 在含v i 的第一个非零值1 的列中，除1 外其它元素全为零。 令，( a ) = a l ，a 2 ，。 ) 为 1 ，叫的子集，其中。t 为m ( a ) 的第i 行中第一个非零值 所在的列，则f 是从子空间格k ( q ) 到布尔格b 。( g ) 的一个秩，保序映射 1 4 洋 雌一一 即m 肛卜玩旧 叫 劭限一 m h 大连理* 搬学硕士学位谶盘 壤4 1 。如暴，= l ，3 ，4 ，鳞瑟7 ，瓣m 溶) 骞影式 1$ o 0 0 0 o 0 00 1o o圭 o 0 其中 为c f ( q ) 上的任意谯 事实土，鳃暴绘定令爨会s = 8 l ，半2 ，a 女 ，燹糍一类滤足上嚣三条性凄静辑襻藏 形矩阵m ( a ) 岛鳓畦应， 淡示在掰泌) 巾第i 行鳇+ 鲍个数，计算罐得x = 珏一t k - k + i ， 缀阵m ( a ) 中所有+ 的个数t ( s ) = 坠1 沁，则与集合s ； a 2 ，讯) 对应的所有行 梯减形矩阵的个数为矿( 扪也就是说，对于任意一个k 元子集s 一 0 1 ，a 2 ，) ，有 毋葶令手空鬻譬之辩应。 在k n u t h 的基础之上。麓军【5 2 l 又得到了下面的缡粜，这对子熬，子空间模拟提供了 熙好的方法 定理4 6 设驴慧岛的一令捶痿，玩汹建& 中满足性质势的鼹有子集，氪l l 农子空间 耨上有性震p ( 鼋) ，使蒋a 磊( 譬) 潘庭醺覆轳汹当菇仅璺( a ) 涛慧瞳覆护 十崔论4 1 厶( q ) 【矽l 是k ( g ) 中满足性质p ( q ) 的所有予嚣间，则有如下一对恒等式 陬删= 1 “。2 。1 ) s e 墨n 溯 嗡( 口) 潲i = 产 ( 4 2 2 ) s 毋h 【p 】 摄然，在上嚣推论中，些q l 时，巷_ 恒等式4 2 2 趋于恒等焱4 2 + 1 对手蠡露瓷鸯翡所毒；豹个数t ( s ) ，羧下来绘鑫絮瓣另岁嚼示及耀关懿嚣令蹙遴。 对于任意个( 0 ，1 ) 穿剃t f ，= 虮铆，定义 n - - 1 m 扣) = 馘( 域再+ + 嘲， i ；l 其中研= 1 一姚，嘶= 0 ，j 换句话说， 舢洳) 等于序列 中每个1 之后0 的个数 的和，也即序列伽的逆序个数 设x = 茹l ，聋2