关于错排数的一些研究

《关于错排数的一些研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、东北大学硕士学位论文关于错排数的一些研究姓名：刘丹申请学位级别：硕士专业：应用数学指导教师：孙平20050201东北大学硕士学位论文摘要关于错排数的研究摘要·错排数是组合数学中一种重要的特殊数，它与概率论也有密切的联系。本文对错排数进行了比较详细的研究，对错排数的表达式及它的递推关系进行了讨论，其中利用了发生函数对错排数的递推关系进行了推导，并详细讨论了错排数及其递推关系之间的互推过程。此外还研究了错排数的推广形式。另外，本文讨论了概率方法在错排数的表达式的推导上的应用。在本文的最后利用C++语言进一步讨论了错排数的输出程序。关键词：错排数发生函数递推关系数学期望东北大学硕士学位论

2、文ABSTRACTSomeResearchesontheNumberofDerangementsAbstractThen岫berofderangementsisanimportantnumberincombinattics．Thereisacloserelationbetweenthenumberandtheprobability．InthisPaoerwegiveawholediscussiononthenumberofderangementsanditsrecursiverelation，andgiveaderivedprocessontllenumberofderangeme

3、ntsanditsrecursiverelationbyusingthegeneratingfunctionindetail．InthisPagIerwealSOgiveageneralformofthederangementproblem．Inadditionwegiveanapplicationofpmbabilisticmethodsintherepresentionofthenumberofderangements．Lastly，wegivealloutputprocedureon坊enumberofderangementsbytheC++language．Keywords

4、：thenumberofderangementsgeneratingfunctionrecursiverelationmathematicalexpection．．1II-独创性声明本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：刘丹日期g2005年2月学位论文版权使用授权书≯竹wf≯{{№p’本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定

5、：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。(如作者和导师同意网上交流，请在下方签名；否则视为不同意。)学位论文作者签名：导师签名：签字日期：东北大学项士学位论文第一章绪论1．1错排问题的简介错排问题是组合数学发展史上一个重要问题。令{唧)(1≤k≤胛)是{珂}，珂∈Ⅳ的一种排列a如果每个元素都不在其原始位置上，即G1≠1，a2≠2，⋯，an≠疗那么这种排列称为错位排列，或错排、重排。若用或表示其个数，则有通项公式以及递推关系：见刊套等∽¨，见=(玎一1)(见一，+o

6、n一：)，D1=0D2=1(1．1．2)见=nD一1+(一1)1，D1=oD2=1(1．1．3)(1．1．1)式由尼古拉·伯努利(NikolansBernoulli)和孟特马特fP．R．deMontmort)用递归法得出，随后棣莫弗(DeMoivre，Abraham)应用容斥原理获得了该式。1．2错排问题的由来孟特马特(P．R．deMontmort)1708年研究了一个称为“相遇”(TreiZe或Rencontre)的纸牌游戏，规则如下：发排者洗好A，K的13张牌后，每次发牌一张，发第一张牌时说“1”，发第而张时说“2”，如此下去，发牌结束后开始翻牌，如果翻过后牌的点数与发牌时所说

7、的正好一致，那么发牌者获胜。例如，若所发的第3张牌翻过来其点数正好是“3”或第11张正好是“J”，即发牌者获胜。东北失学硕士学位论文第一章绪论这一纸牌游戏实际上是组合学中限位排歹

8、j问题，孟特马特(P．R．deMontmort)因解决此游戏中获胜的概率而在组合学的历史上得以留名。错排问题也称为伯努利一欧拉(Bernoulli．Euler)错装信封问题：某人写了开封信，并且在行个信封上写下了对应的地址，问：把所有的信签装错信封的情况共有多少种?欧拉(Euler)解出了这