多重集的限位限邻排列计数问题的研究.doc

怎克教約肝托址it GuangDong Polytechnic Normal University 毕业设计（论文） 题 目：多重集的限位限邻排列计 数问题的研究 （英文）： The Study on Enumerating Problems of the Arrangements Limited Its Elements Locations And Neighborhoods of a Multi-set 院 另|J： 计算机科学学院 专 业：数学与应用数学（师范） 姓 名： 杜逸娜 学 号： 2009035344024 指导教师： 黄凤英 日 期： 2013年5月 多重集的限位限邻排列计数问题的研究 摘要 本文将多重集的限位排列和限邻排列这两种情况结合起来，研究了多重集 { 2?％,25，..?,2?务}的作成的任何两个q仃=1,2,???/）均不相邻且限制了⑷，勺，為 的位置的全排列，利用容斥原理，得到了它们相应的计数公式，同吋介绍了它们在实际 牛活屮的一些应用。 关键词多重集；限位限邻；排列计数；容斥原理 The Study on Enumerating Problems of the ArrangementsLimited Its，Elements5 Locations And Neighborhoods of aMulti-set ABSTRACT Combining the location- limited and the neighbor- limited of multisets，arrangements problems, we study the arrangements of a multiset { 2 ?山，2 ? a2，…,2 ? an } which limit any two % (i )not locating together and limit the locations of 4， a2 . . By Inclusion-Exclusion Principle, their enumeration formulas are obtained. Moreover, some applications of them in real life arc introduced? Key words： Multi-set; Location- Limited And Neighborhood-Limited; Enumeration of Arrangement; Inclusion-Exclusion Principle 目录 TOC \o 1-5 \h \z HYPERLINK X iA.nA2n-nA,|. k=\ IG] i2 定理C设S是有限集，A.BqS,则 5-aub| = |5|-|a|-|b| + |a ab|. 定理D设S是有限集，A,B,CuS,则 \s-aubuc\ = |s|-|a|-|b|-|c|+|a ob\+\a qc\+\b nc|-|A ns nc|. 2.3多重集的限位的排列计数问题 引理2.1以厂(2,1,2,3)表示由2个%, 2个如…匸个色作成的吗不在第一位,偽 不在第二位，偽不在第三位的全排列的个数，则 厂(2” ,1,2,3) = (8n3-28n2+56n —44)(2〃一3)!. 证明：以S表示由2个⑷，，2个色,???,2个色作成的所有全排列之集，则 |S| =（2〃）！2!2!??…2! |S| = （2〃）！2!2!??…2! （2/1）! 2” 以A(i = l,2,3)表示S屮q排在第i位的全排列之集，则 厂（2”,1,2,3） 厂（2”,1,2,3） S—A〕U A2 U A3| I a, I a, nx2 nx3|（加?3）! 2〃_3 =|s|—|a』一肉|—肉|+|4】门每|+|￡ riA3 + A2 门人—〔A ha2 riA3. Hu IaI = Ia2I = |a3| = ^ 2一2A n^l = I a, nx3| = | a2 nx3 2一2 所以 ⑵ 2—1）!n-l v 22“-3：!十3（ ⑵ 2—1）!n-l v 2 2“-3 2”t 2 （r 一 28用 + 56〃 一 44）（2〃 一 3）! 2J 2.4多重集的限邻的排列计数问题 引理2.2以/(2〃)表示由2个％, 2个吆…，2个陽作成的任何两个勺 （心1,2,???川）均不相邻的全排列的个数,求证: 2)空(一1) 2)空(一1)僧0-灯!L=(\ K 2十 证明：以S表示由2个绚，，2个色,…』个勺作成的所有全排列之集，则 ■ ■ (2/0! =(2h)! 1 |_2!2!??…2!~ T 以A;.（l ； //）表示S屮有