（计算数学专业论文）恒等式的q模拟及组合证明.pdf

大连理工大学硬士学位论文 摘要 恒等式的组合证明或组合解释赋予了恒等式一定的计数意义，组合证明最常用 的方法是分别用两种不同的方法对恒等式的两端进行计数，一般通过构造两个集合 之间的双射，这两个集合的个数分别表示恒等式的两端，从而根据双射的一一对应 性证明恒等式本文也正是采用了这种方法对恒等式进行组合证明，从而揭示组合 证明的一般方法 在组合恒等式中，q 一恒等式是一类特殊的恒等式，其中一大部分是关于离散 变量恒等式的口- 模拟，这里g 是个参数，它具有很多的计数意义，因此对口恒 等式的证明受到人们的广泛关注人们用各种各样的方法进行研究，本文主要采用 分拆的方法来给出一些铲恒等式的组合证明 本文给出了一些重要的二项式系数恒等式的组合证明或组合解释，并从分拆的 角度给出了一些口恒等式的组合证明，其中突出的成果是给出了平方和恒等式的 一个直接的组合证明并给出了偶数平方和与奇数平方和的口模拟及组合证明 文章主要内容可概括如下t 1 介绍了一些与鼋模拟有关的基本知识和基本概念，如：分拆，f e r r e r s 图，偏序 集，格，组合证明，二项式系数等 2 给出了一般布尔格上一些重要的恒等式及其组合证明或组合解释 3 引入口- 模拟的概念，从分拆的角度给出了一些q 恒等式的组合证明 4 给出了恒等式各。七2 = ( 2 寸2 ) 的个直接的组合证明并从分拆的角度分别 给出了恒等式麓- ( 2 ) 2 = ( 对2 ) 和警。( 2 女一1 ) 2 = ( 2 寸1 ) 的口模拟及组合 证明 关键词：组合恒等式；分拆；f 幻螂图；双射；酽模拟；组合证明； g a n a l o g u ea n dc o i n b i n a t o r i a lp r o o fo f i d e n t i t i e s a b s t r a c t b yt h ec 0 d 如i n a t o r i a lp r o o fo rc o d i b i n a t o r i mi n t e r p r e t a t i o n ，t h ei d e t i t yi se q u i p p e d w i t hc e r t a i n u n tm e a 丑i n g t h em o s tg e n e r a l 啪yi nt h ec o m b i a t o r i a lp r o o fi st oc o u n t 七w os i d e 8o ft h ei d e t i t yb yt w od i 丑蔚e n tm e t h o d s g e n e r m y ，t h r o u 曲b u n d i n g8b 玛e c t i o f r o mo n es e tt oa n o t h e ro n e ，t h en u l b e ro ft h et w o8 e t 8r 皓p e c 七i v e l yr e p r e s e n t st h et w o s i d e so ft h ei d e t i 够b e c a u s eo ft h e1 1p r o p e r t yo f b 匀e c t i o n ，t h ei d e t i t yi 8p r o v e d t h i s t h e s i sj u b t 印p l i t h i sm e t h o dt o 百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 8 lp r o o a s8r e s u l t ，a g e n e r a la p p r 0 础t oc o 刀出i n a t o r i a lp r o o fi 8m l l s t r a t e d g i d e n t i t yi sac e r t a i nc 1 晒si d e n t i t yi nc o 工i l b m a t o r 试i d e n t i 够m 0 8 tg i d e n t i t i e s 壮e 哥a n a l o g u 鹤0 fi n d e n t i t i 髑丽t hd i s c r e t e 州a b l e ，w h e r e 口i sap a r a 1 e t e r 口一a n a j o g u eo f i d e n t i t yh a sm u 出c o u n tm e a 皿i n g s o 罢如i n gc o m b i n a t o r i a lp r o o f0 f 鼋一i d e n 虹t yi sv 缸y m e 眦i n g 1 1 i nt h et h e s i s ，w e 舀v ec o 珈【b i n a t o r 试p r o o f0 f8 0 m e 口一i d e t i t i e s1 1 s 沁i t e g e r p a r t i t i o n i nt h et h 嚣i ss o m ev i t a li d e t i t i 鹤w i t hb i i l o m i m e 伍c i e n ta r e 西v e nw i t ht h e i rc o l - b i n a t o r i a lp r o o f a 丑dt h e 铲a a l o g l l e 8o fs o m ei d e n t i t i e 8 村eo 丘e r e dw i t hc o r r e s p o n d i n g c o 1 _ b i n a t o r i 出p r o o fu s i n gi n t e g e rp 龃t i t i o n e s p e c i 缸i y io n er 锄a r k a - b l er e 8 1 j 1 ti st h a 上a n e wc o m b i n a t o r i a lp r o o fo ft h es q u a r e - s u m si d e n t i t yi so b t a i e d w ba l s o 西v ec o 刀小i n a t o r i a lp r 0 0 fo ft h es u n l so fe v e n8 q u a r e s ，o d ds q u a r e sa dt h e i rq a n 出。弘e su 如g 越e g e r p a r t i t i o 。i h em 舡nc o t 址e n t o ft h i st h e s i sc 缸b e8 u m l a r i z e da sf o u o w s ： 1 i t r o d u c er e l e v a n tb a s i ck n a w l e d g ea j l dc o n c e p ta b o u ti n t e g e rp a r t i t i o n ，s u c h 嬲i n t e - g e rp 盯t i t i o n ，f b r r e rf a p h ，p 0 s e t ，l a t t i c e ，c o m b i n a t o r i a lp r o o eb i n o m i a lc 0 锄c i e n t a n ds oo n 2 s o m ei n l p o r t a 丑ti d 钮t i t i 8a r ep r o v i d e dw i t ht h e i rc o 刀出i n a t o r i a lp r o o f o r m b i a t o r 谢 戤镀弘甙雠i o no n 也eb o 吐el a m c e8 n 3 i t r o d u c et h ec o n c e p to f 口- a a l q g u e q - a n a l q g u e so fs o m ei m p o r t a 皿ti d e n t i t i e sa r e g i v e n 谢t ht h e i rc o m b i a t o r i 越p r o o fu s i n gi t e g e rp a r t i t i o 4 w e 咖an e wc 0 曲i n a t o r i a lp r 0 0 fo f t h e i d e n t i t y 警l 七2 = ；( 对2 ) w e8 1 s o 咖 c o m b i n a t o r i a lp r 0 0 fo ft h es u n l s0 fe 、，e ns q u 8 r e s ，o d ds q u 且r e sa 1 1 dt h e i rg a n 8 l o g u e 8 1 1 s i gi n t e g e rp w t i t i o n s k e yw b r d s ： c o n l b i a t o r i a li d e n t i t y ；p a r 七i t i o n ；r r 盯8 驴a p h ；b 置j e c t i o n ；口_ 卸a l o g u e ；c o m b i n a t o r i a lp r o o i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作及取得 研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写的研究成果，也不包含为获得大连理工大学或其他单位的学位或 证书所使用过的材料 作者签名，逸：! ! 豸日期；2 蝉 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解”大连理工大学硕士、博士学位论文版权 使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印 件和电子版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段 保存和汇编学位论文 作者签名 导师签名 连尘豸 大连理工大学硬士学位论文 1 引言 组合数学是既古老又年轻的数学分支，它的渊源可以追溯到公元前2 2 0 0 年大 禹治水时代中外历史上许多著名的数学游戏是它古典部分的主要内容公元1 6 6 6 年，德国著名数学家莱布尼兹为它起名为”组合学”，并预言了这一数学分支的诞 生1 9 4 0 年以来，特别近年来，随着电子计算机科学，计算数学，通信以及许多 学科的发展，组合数学这门历史悠久的学科得到了迅速发展组合数学不仅在计算 机，人工智能，过程控制和空间技术等新兴学科技术中有着重要的应用，而且在一 些看似与数学关系不大的企业管理，交通规划，金融分析等社会科学领域都有重要 的应用价值，因此组合数学的方法和思想越来越受到人们普遍的重视组合数学研 究的领域有很多，如：计数组合学，代数组合学，图论及其算法，组合优化，组合 设计，恒等式的口模拟及其组合证明等等 本课题所属的研究领域是恒等式的q 模拟及其组合证明，它对于组合数学的研 究有非常重要的意义，赋予了恒等式一定的计数意义，而且使数学的各学科知识与 组合数学有机的结合在一起，一壹以来都深受组合学家们的重视 分拆理论产生于十八世纪，e u l e r 首先对它进行研究，其后经c a l e y ，g a u s s ，j a c o b i ， l a 辱a n g e ，s c h u r 还有m 砌讧a h 0 等人发展近代a d r e w s 作为当代分拆理论的领导 人对充实这个领域做出了巨大的贡献几乎所有的分拆定理都与组合恒等式或基本 超几何级数有关g e a n d r e w s 【2 】早在1 9 7 6 年利用f e r r 口s 图给出了一些与分拆 有关的q 一恒等式的组合证明 r p s t a n l e y 【4 q 在1 9 8 6 年利用r r r e r s 图给出了几 个口一恒等式的组合证明g e a n d r e w s 【q 在1 9 9 1 年利用分拆的方法给出了一些 g 麟系数恒等式的组合证明 c h 一l t o u f l5 1 在2 0 0 3 年利用f h r e r s 图给出了一个 g a u s s 系数恒等式的组合证明g r e t t 和 岫e l 例于2 0 0 4 年从分拆的角度给出 了二项式系数恒等式。3 = ( “+ 1 ) 。的一个哥模拟及铲模拟的组合证明，之后 w 打a ”【4 6 】又给出了它的一个更简单的g - 模拟形式同年，s c h l o s s e r 【3 1 做了推广， 利用口- 级数给出了k 】护，m = 1 ，2 ，3 ，4 ，5 的哥模拟形式所以对于这类口一恒等 式利用分拆的方法给出他们的组合证明是很有意义的 大连理工大学硕士学位论文 2 绪论 本文主要从分拆的角度给出了一些恒等式的口一模拟及其组合证明，首先我们 介绍一些与之相关的基本知识和基本概念 2 1 整数的分拆及f e r r e r g 图 一个整数n 的分拆入指的是一个非增整数序列a = ( 1 ，a 2 ，h ) 使得入1 + a 。+ + 儿= n 相当于把个无区别的球放进n 个无区别的盒子，盒子中允许放 一个以上的球，当然也允许空着凡是分拆的部分不同的分拆法的数目称为分 拆数令州i = a 1 + 2 + + k 为分拆 的权重，有时记为阱 p ( n ) 指整数n 的分拆数m ( n ) 指整数n 的恰好有七个部分的分拆数p k ，n ) 指整数n 的最多有个部分每部分不超过j 的分拆效例如，整数5 可分拆成， 1 + 1 + 1 + 1 + 1 ，2 + 1 + 1 + 1 ，3 + 1 + 1 ，2 + 2 + 1 ，4 + 1 ，3 + 2 ，5 ，所以p 1 ( 5 ) l ， p 2 ( 5 ) = 2 ，船( 5 ) = 2 ，m ( 5 ) = 1 ，p 5 ( 5 ) = 1 ，p ( 3 ，3 ，5 ) = 3 ，等等为了方便，我们令p ( 0 ) 和p 0 ( o ) 等于1 f e r r e r s 图是研究分拆的一种有效的工具假定n 分拆成n = n 1 + n 2 + + n k ， 其中n 。n ：2n 我们将它排列成阶梯形的，左边看齐，第1 行n 1 格，第2 行竹2 格，第行n 格，即上层的格子数不少于下层的格子数这样的图 象称为n r r e r s 图 为了方便f e “s 图的格子也可以代用圆或点，既用格子中心的圆或点代替格 子 f e r r e r s 图有如下一些性质： ( 1 ) 每一层至少有一个格子 ( 2 ) 行与列互换，即第1 行与第1 列，笫2 行与第2 列，也就是如图 2 1 所示沿对角线旋转1 8 0 。的结果仍然是f e r r e r s 图后一个f 栅e r 8 图称为前一个 f e r r e r s 图的共轭 利用f h r ”s 图可以推出如下关于整数分拆的有趣结果假定n 和都是正整 数 引理2 1 整数 拆分成个数的和的分拆数，与将n 拆分成最大数为的分拆数 相等 3 查尘董! 堡竺茎堕生堡垫墨墨盒至塑 整数n 拆分成个数的和的分拆方案可以用行的f h r 盯s 图来表示若n = n l + n 2 + + 竹k ，其中n 1 n 2 n k ，则胁r e r s 图第一行有n 1 个格，第2 行有 n 2 个格，第行有n k 个格例如，2 4 = 6 + 6 + 5 + 4 + 3 ，它的f 妇r 8 图 像如图2 2 ( a ) 所示 2 4 = 6 + 6 + 5 + 4 + 3 ( a ) l l l i 2 4 5 + 5 + 5 + 3 + 2 ( b ) 由于r m 哪图的共轭图仍然是f 栅e r 8 图，例如图2 2 ( b ) 是图2 2 ( a ) 的共轭图， 它表达了整数n 拆分成最大数为的一个分拆反之亦然这就证明了引理2 1 引理2 2 整数n 拆分成最多不超过个数的和的分拆数，等于将n 拆分成最大数 不超过的数的和的分拆数 引理2 2 的证明与引理2 1 的证明类似，我们可以将引理2 1 看作引理2 2 的推 论 引理2 3 整数n 拆分成互不相同的若干奇数和的分拆敷，与n 拆分成有自共轭 f e ”t r s 图的分拆敷相等 假定拆分成个互不相同的奇数t2 n 1 + l ，轨2 + 1 ，2 n k + l ，其中n 1 n 2 n k 可构造一自共轭的五h r 盯s 图如图2 3 所示例如，1 7 = 9 + 5 + 3 ，虽 然是举例说明，但证明的道理已在其中竹拆分成互不相同的若干奇数和的分拆与 拆分成其f e r r e r s 图像为自共轭图象的分拆一一对应反过来也是一样 利用f 打r e r s 图还可以证明， 定理2 1 数n 拆分成不超过女个数的和的分拆数，等于将n + 南拆分成正好个 4 大连理工大学硬士学位论文 lill + li + 数的分拆数 2 2 偏序集，格 9 + 5 +3 = 1 7 图2 3 ： 偏序集是一种特定的集，它是一类主要的序关系集，具体的说，集合e 连同其 上的偏序r 构成的关系集( e ，r ) ，般记为p = ( e ，) ，所谓偏序( 或序关系) 是一 类具有自反性，反对称性和传递性的二元关系，例如，数之间的不大于关系，自然 数之阀的整除关系，集合之间的包含关系等把集合e 的基数称为偏序集p 的阶， 阶为有限值的偏序集称为有限偏序集而在p 上，对于任意元索z ，区间陋，胡均 为有限偏序集时，称p 为局部有限偏序集这两类偏序集是组合理论中的主要研究 对象偏序集上所有链的长度的最小上界或上确界，称为偏序集的长度，记为f ( p ) 偏序集的最大元，最小元： 偏序集p = ( e ，s ) 的子集s 中的元素o ，若在s 中不存在其它元素o ，使得 o z ，则称。为s 上的极大元对称的，若在s 中不存在其它元素茹，使得zsn ， 则称口为s 上的极小元若取s = e ，则分别称。为偏序集p 的极大元，a 为偏 序集p 的极小元当p 为有限偏序集时，其极大元，极小元总是存在的，若对于 尸的所有元素茹均有。sn ，则称。为偏序集p 的最大元对称的，若对于p 的所 有元索。均有o z ，则称n 为偏序集p 的最小元+ 偏序集并不总有最大元，最小 元若它时有限全序集，则它总有最大元和最小元 格是一类代数结构它是建立在偏序集p = ( es ) 之上的，由f 的任意元素 z ，掣构造的如下两个集合1 ( z ，v ) = 扛eizs 可z 及2 ( z ，g ) = 0 ez z ，z 它们作为p 的子集均为偏序集，一般不一定有最大元或最小元若对p 的任意元素毛，1 ( 霸y ) 均有最小元，2 ( 。，们均有最大元，则称p 为格，并记为 c 5 塑型! 董! 堡董塞塑生坚壑墨塑鱼至塑 在格上，把1 y ) 和其最小元的对应关系视为一类二元运算，称为z 和f 的交，记为。 对称的，把2 ( 毛) 和其最大元的对应关系视为。和9 的结，记 为。v ”它们是格上的最基本的运算这两类运算满足： ( 1 ) 同律z v z = z ；正 。= 茁 ( 2 ) ；芒嘉廷律霍v = 掣v z ；z = 可 o ( 3 ) 结合律z v ( 可v 2 ) = ( zv ”) vz ；z ( 可 z ) = ( o 掣) 2 ( 4 ) 吸收律引、v ) = z v0 v ) = z ，其中。，f 和z 均为e 的任意元素，因 此格又可视为满足上述四条规律的代数结构c = ( e ，v ， ) 2 3 映射及组合证明 设j ( m ，) 或m 为m 到的映射，的集合；对于每一个m ，通过，就 对应到z 的象f ，记为”= ，( z ) 我们通常写，：ml 一来代替，j ( m ，) ， 当m 和有限时，m = ml ，= i i ，我们可以给m 的元素编号，设m = 轧，。 ，显然，给一个，就等价于给一个的m 个元素的表，比方说， 9 ，耽，) ，它们依某一顺序，允许重复的列出那么所谓给出这个表就意味着 玑是矗( 1 t m ) 的象：玑= ，( ) ，换句话说，给一个，就等价于给出一个属于 村的m 元组，也称为一个一选择这样，就找到了把，( m ，) 记为m 的理 由 引理2 4 有限个有限集合的乘积集合的元素个数满足 证明： 事实上，m 元组 1 ，抛， 的个数等于1 中- 的可能选择数j 1f 乘 以2 中抛的可能选择数i 2l ，等等，乘以中鼽的可能选择数l k1 ( 因为 这些选择是相互独立的) 由这个引理容易证得下面这个定理 定理2 2 m 到的映射个数有下式给出： j ( m ，) = l 村j = i l i m i 对每一个子集ac m ，我们表示 ，( 且) ：= ，( z ) i 。a ) 这样就定义了一个从b ( m ) 到8 ( ) 内的映射，称为，到m 的子集集合上的扩张 这也用，表示其中b ( m ) ，8 ( ) 分别表示m ，的所有子集构成的集合 6 m | | m m 试 i l m m 曲 大连理工大学硬士学位论文 对所有口，m 的子集 ，一1 ( ) ：= zl ，( 正) = 掣 可以是空的，称为由，得到的口的原象或逆象 下面我们介绍什么是组合证明，首先，我们回忆一下代数学中的知识， ( 1 ) 如果两个不同元素的象也不同：z t 。2 = 辛，( z 1 ) ，( 。2 ) ，埘就称为 是单射的( 或叫做一个单射) ； ( 2 ) 如果的每个元素都是m 中某一元素的象：，j z m ，使得，( 。) = v ， ，就称为满射的( 或叫做一个满射) ； ( 3 ) 如果，既是单射的又是满射的，就称为双射的( 或叫做一个双射) 在( 3 ) 这种情况下，的逆或反，记为，定义y = 厂1 ( 。) 当且仅当z = ，( ) ， 这里。m ， 要数一个有限集合e ，换句话说，确定其大小，原则上就是建立e 列另个元 素个数已知的集合f 上的双射；从而le i f i ，这也就是计数问题中所谓的组合 证明 2 4 排列，置换，：项式系数 对于每一个不小于1 的整数，我们记 定义2 1 集合的一个一徘列( 1 sn = l 1 ) 就是一个从嘲到的单映射 。，我们用0 瑶( ) 来表示的排列的集合 因此，给出这样一个n ，首先等价于给出的个元素的子集 b = o ( 嘲) = 如( 1 ) ，n ( 2 ) ，a ( ) ) 其次，等价于给出了b 的元素一个从1 到女的编号， 最后，等价于给出了的个元素的全部排序的子集，也经常h q 做的一个 一排列 定理2 3 的女一排列个数( 1 k n = ) 等于 z 如( ) f = ( n h = n ( 阼一1 ) ，- ( n 一自+ 1 ) 证明t 显然，1 ( 【嘲) 的象。( 1 ) 有n 种可能选择；o ( 1 ) 选定后，因为口是单射的， 。( 2 ) o ( 1 ) ；o ( 2 ) 就只有余下的一1 ) 中可能；类似的，因为a ( 3 ) n ( 2 ) ，n ( 3 ) 。( 1 ) ，对n ( 3 ) 只有m 一2 ) 种可能的选择，等等；最后，对n ( ) ，恰有余下m 一+ 1 ) 种 可能的选择 7 堡尘茎：堡竺塞竺生塑墨望鱼垩塑 因此，n 的个数等于所有这些选择数的乘积，即等于 扎( 礼一1 ) ( n 一2 ) ，( 札一七+ 1 ) 注：如果 n ，则( n ) = 0 定义2 2 集合的置换就是到自身的双射，我们用口( ) 表示的置换集合 定理2 4 ( i l _ n 1 ) 的置换个数等于n ! 证明： 仿照上面定理的证法易得证 定理2 5 用8 ( ) 来表示的子集的集合，的女子集个数用( ：) 来表示，则 ( ：) = 1 8 ( 驯= 警= 生业掣 一 型一fn 、 七! ( n 一蠡) !扎一七 证明： 首先证明等式( ；) = i8 ( ) 卢警，其它几个都是它的直接推论，如果= o ，则 警= 1 由于i 嚣( ) 1 只含的空子集，从而f8 ( ) 1 假设l ，每个排列口地( ) ，对应着b = ，( o ) = ( n ( 1 ) ，n ( 2 ) ，n ( ) i 魄( ) l ，则，是( ) 到取( ) 的映射，使得对所有b ( ) ，有 ，_ 1 ( b ) l = ! 因为b 有k ! 种可能的编号现在当b 跑遍取( ) 时，互不相交的原象集合，1 ( b ) 完 全覆盖了狐( ) 因此，( ) 的元素个数等于所有l 厂1 ( b ) i 的和，这里b 魄( ) ， 即有： ( n ) k = l 阮( ) i _ i ，- 1 ( b ) 障! i 嚣( ) l 且 因此，1 雠( ) 】= 睁得证 定义2 3 整数( ：) 叫做二项式系数 2 5 组合，允许重复的组合 当从n 个元素中取出r 个而不考虑它的顺序时，称从n 中取r 个的组合其数 目记为g ( n ，r ) ，印或( ? ) 允许重复的组合指的是从a = 1 ，2 ，n 中取r 个元素 n 1 ，0 2 ，畔) ，毗a ， i = 1 ，2 ，r ，而且允许口产o f ，t j 例如，a = 1 ，2 ，3 ) ，取两个作允许重复的组合，除了不重复的组合( 1 ，2 ) ，( 1 ，3 ) ， 2 ，3 ，之外，还有 l ，1 ) ， 2 ，2 ) ， 3 ，3 定理2 6 在n 个不同的元素中取出r 个进行组合，若允许重复，则组合数为( n + 二q ) 8 大连理工大学硬士学位论文 证明： 只要证明允许重复的组合与从n + r 一1 个不同的元素中取出r 个作不重复的 组合一一对应定理就获得了证明 先证明n 取r 可重复的组合和从n + r 一1 个中取r 个的不允许重复的组合一 一对应 不失一般性，假定n 个不同的元素分别为1 ，2 ，”从中取r 个作允许重复 的组合n 1 ，。2 ，口，由于存在重复故令n lsn 2 o ， 从 n 1 ，0 2 ，o ， 引出 。l n 2 + l ，o k + 瓦1 ，。r + f 了) 使每一允许 重复的组合 n 1 ，n 2 ，嘶) 对应于一个不允许重复的组合 口1 ，n 2 + 1 ，o k + 一 l ，a ，+ r 一1 ) ，令后者为 6 1 ，6 2 扣，) ，即6 k = k + 一l ，= l ，2 ，r ，其中 b l 幻 b ，茎n + r 一1 故从1 到n 中取r 个允许重复的组合，对应于一个从 1 到n + r 一1 中取r 的不允许重复的组合 反之，从 l 、2 ，n + r 一1 ) 中取r 个作不重复组合p 1 ，6 2 ，k ) ，不妨设b 1 b 2 ksn + r 一1 构造b l ，6 2 1 ，蚝一2 ，6 r r + 1 ，显然有b 1 茎6 2 1 b 3 2 6 r r + 1 令口 = 6 鼍一知+ l 七= 1 ，2 ，r ，故0 110 2 口rs 礼故 从1 到n + r 一1 取r 个作不重复的组合，和从1 到n 取r 个作允许重复的组合一一 对应这就证明了在n 个不同元素中取r 个作允许重复的组合其组合数为( ”+ = 。) 允许重复组合的典型模型是取r 个无区别的球放进n 个有标号的盒子，而每个 盒子中的球数不加限制，允许重复的组合数即其方案数 定理2 7 r 个无区别的球放进n 个有标号的盒子，每个盒子申可多于一个，则共有 ( “弋。) 种方案 9 大连理工大学硬士学位论文 3 子集格上一些重要的恒等式 上一章，我们已经大概介绍了什么是组合证明。及组合证明的思想，方法，并 引入了二项式系数( ：) ，这一章将给出一些关于二项式系数的重要恒等式及它们的 组合证明，通过这些例子将使我们进一步理解组合证明的思想和方法 3 1 布尔格及子集格 布尔格是一种特殊的格，它是与布尔代数b 。( 2 。；u ，n ) 同构的格，布尔格的 结运算和交运算分别对应于布尔代数的并运算和交运算 这里所说的布尔代数，是布尔( b 0 0 1 e ，g ) 于1 8 4 7 年及1 8 5 4 年研究思维规律 ( 逻辑学，数理逻辑) 是提出的，而它作为一种特殊的格则是戴德金( d e d e l d d ，j w r ) 后来提出的所谓布尔代数，是指一个有序的四元组( b ；a ，v ，) ，其中b 是非 空集合 和v 分别是b 上的二元运算，而“”是定义在上的一个一元运算，并 且满足下列条件：对于任意砒6 ，c b ( 1 ) n b = 6 口；o v6 = b v o ( 2 ) 口 ( 6 c ) = ( 口 6 ) c ：口v ( 6 vc ) = v6 ) v c ( 3 ) ( 口vb ) = 口；v m a6 ) = o ( 4 ) ( o 扫) v ( b c ) v ( c n ) 军( 。vb ) vc ) ( c va ) ( 5 ) ( o d ) v6 = 嘶( n v n ) 6 = 6 1 9 0 4 年，亨廷顿( i 衄廿卫g t o n ，e v ) 发现：若集合a 有一个二元运算v 和一个 一元运算定义。m = ( n v 矿) ，并满足： ( 1 ) v6 = 6 - n ； ( 2 ) ( 口 b ) v ( = 口； ( 3 ) v ( 6 vc ) = ( 。v6 ) vc ； 则a 是布尔代数这是布尔代数的一个典型结果1 9 6 7 年，1 9 鹋年戈莱兹 ( g r 龇z e r ，g ) 和莫肯济( m 出h 1 z l e ，r m ) ，塔尔斯基( t 凸姻k i ，a ) 分别独立的进一步 发现布尔代数可仅用一个恒等式来定义 定义3 1 2 f _ 为n 元集合 1 ，2 ，n 的所有子集构成的集族，按照包含关系t - 至”， b = ( 2 h ，) 是子集格，简记为8 。，其上的结运算z v 为集。和集f 的并集，交运 算。 g 为集z 和集的交集 算。 g 为集z 和集的交集 堡尘董! 堕堇苎笪生堡垫墨望盒堡塑 3 2 一些重要的二项式系数恒等式及组合证明 一般二项式系数 ( ：) = 业芒铲= 耐， 。， 可以表示n 元数集( 1 ，2 ，n 的子集的个数关于一般二项式系数( ：) 有一些 重要的恒等式如下t 注；这些恒等式根据二项式系数的定义及归纳法可容易证明，这里只给出它们 的组合证明或组合解释 下面的证明中，用嘲表示集合 1 ，2 ，n ) 定理3 1 仁项式定理j 设z = 可z ，对于每一整数n o ，我们有： 扛+ f r =熹( 驰诎 = 。”+ ( ：) z n 一1 v + ( ；) z n 一2 v 2 + + ( 。二，) z ”一1 + ”“ 证明： 首先考查下列展开式系数g ，： + ) “= p 1 岛r = 1 扩，其中只= z + 口，i h ，项。是通过选择n 个因子只0 ) 中的个，用个因子中 的“z ”项乘以余下一) 个因子中的“”项而得到的，所以f = n k 因此系数 仉，= 仅。一k 等于在n 个因子中选出个不同因子最的选择数为( ；) 即原式成 立得证 例1 ：如果z = = 1 ，那么麓o ( ；) = 哥，因此( 1 ，2 ，n ) 的子集总数为2 n 例2 ：如果z = 一1 ，口= 1 ，则 耋( _ 1 ) q ) 乩 ( 3 。2 ) ( 一1 ) ( ：) 乩 ( 3 删 七= 0 、。 换句话说，集合 1 ，2 ，n ) 的偶”子集与崎”子集一样多 定理3 2 恒等式 f ，”+ m + 1 、： m + l ( 3 2 5 ) 3 4 2 2 3 3 、 一七 n ， + 、 l n 1 1 札 一n 竹膏 ，一， = = ? + mr 。瑚 大连理工大学硕士学位论文 证明： 它们的组合证明都很简单，在这里我们仅给出( 3 2 4 ) 的证明 ( ：) 表示n 元集合m 的所有元子集的个数，设a 为任一k 元子集，若a 包含n ，则a 的取法有瞧二j ) 种；若a 不包含n ，则a 的取法有p i l ) 种所以， ( ：) = ( ：二i ) 十( “i 1 ) 得证 定理3 3 讫n d e m o n d e 一恒等式 ( 。：? = 耋( 。二 慨。脚 证明； 我们知道。+ b 元集合 仲1 ，n 。，m 1 ，m 2 ，m 6 ) 的n 子集的个数为( 。：6 ) ， 现在我们用另一种方法来计算它的n 子集的个数，先从 n 1 ，n 2 ，礼。) 选n 一 个 元素，有( 。三。) 种方法，然后从 m ，m z ，佻 中选余下的 个，有( ：) 种方法， 对i _ o ，1 ，2 ，n ，求和得到n 一子集个数为墨。( 0 。) ( 扫，因此( 。吉6 ) = 坠。( 。三。) ( ：) 成立得证 定理3 4 立方和恒等式 证明| 1 1 】： ( “玎= 薹* 3 江z 令集合s = ( ，t ， ) i o h ，t ，j 竹) ，集合t = ( ( z 1 ，。2 ) ( 。3 ，。4 ) ) l o z 1 。2 n ，o 。l i ( ( ，t ) ，( j ，女) ) ，当九 o o 。 o 口 蔓部分 最大部分g 证明【4 2 l ： 令m = j + ，m 维向量空间- ，m ( g ) 的一个虹维子空间，存在唯一的一组有序 基( ”l ，) 使得矩阵 m 5 廿1 甜2 满足： ( 1 ) 饥，0 = 1 ，2 ，七) 的第一个非零值是1 ， ( 2 ) u 州的第一个非零值出现在陇的第个非零值右侧， ( 3 ) 在含陇的第一个非零值1 的列中，除1 外其它元素全为零 给定一组整数序列1 8 1 0 2 a m ，考虑所有行递减形矩阵使的 第一个非零值出现在第。t 个位置 例如，m = 7 ，= 4 ，( o l ，。2 ，0 3 ，n 4 ) = ( 1 ，3 ，4 ，6 ) 则m 有形式 1 十 00 o 0 00 00 10 01 0 0 其中+ 为g f ( g ) 上的任意值 九表示m 中第i 行的+ 的个数，计算可得扎= j 一啦+ ，得到序列 = ( a 1 ，a 2 ，k ，为至多个部分，每部分不超过j 的分拆令n = 凡，则对应的矩 阵有矿个 反过来，对n 的任意一个符合最多有部分，每部分不超过j 的分拆 ，可令 啦= j 一凡+ t ，则存在矿个上述类型的矩阵 因为行递减形矩阵m 的个数等于i ：2 ( 即m 维向量空闻中b 维子空间的 个数) ，所以定理得证 1 6 十 $ 0 o 0 l 十 十o 大连理工大学硬士学位论文 最多有部分，每部分不超过j 的所有分拆可以描述为e h r e r 8 图在j 的长 方形内的所有分拆，所以由定理4 2 告诉我们p 志 。是f e r r e r s 图在j 的盒子 里的所有分拆的发生函数 4 2一些重要恒等式的q _ 梗拟及组合证明 定理4 3 g 一恒等式 阻= 。 圈。= 剐。 = 。 m 巩= 嘉一 m 分别是定理j 2 中三个恒等式的口模拟 ( 4 2 1 ) ( 4 2 ，2 ) ( 4 2 3 ) ( 4 2 4 ) 证明： 它们的组合证明都很简单，在这里仅用分拆的f e r r e r s 图给出( 4 2 2 ) 的证明+ 倒。表示最多有部分，每部分不超过n 一2 的所有分拆的发生函数令a = ( 入1 ，a 2 ，k ) ，其中n 一2a 1 2 h o 分两种情况： ( 1 ) 当a 1 n 一时，用f e r r e r s 图来表示a ，如图4 1 ”一七蔓m 一蟊+ l 兰七 这种情况下所有分拆的发生函数是 n ：1 。 ( 2 ) 当) l 1 = n 一时，用f b r r e r s 图来表示a ，如图4 2 这种情况下所有分拆的发生函数是口”匿二习。故4 2 2 得证 1 7 一 山 可=_0一k “卜0 。 一矿1 + + + m 塑尘董! 堡竺薹堕筻塑垫墨墨全堡塑 s 七 一七 争兰耙一l 图4 2 ： 定理4