球盒模型的概率问题

1组合数学班级：XXXX姓名：XXXX学号：XXXX1目录摘要................................................................................................................1关键词：........................................................................................................11绪论...................................................................................................................11.1问题的提出.............................................................................................11.2研究现状................................................................................................11.3研究的目的和研究的内容....................................................................21.4本文主要内容........................................................................................22预备知识...........................................................................................................32.1组合知识................................................................................................32.2概率知识................................................................................................22.3球盒模型................................................................................................43球盒模型基本结论...........................................................................................54本文研究...........................................................................................................74.1n个不同的球放入m个不同的盒子的情况.........................................74.2n个不同的球放入m个全部相同的盒子的情况.................................84.3n个全部相同的球放入m个不同的盒子的情况.................................94.4n个全部相同的球放入m个全部相同的盒子的情况.......................125结论与展望.....................................................................................................135.1论文总结..............................................................................................135.2问题与展望..........................................................................................13参考文献......................................................................................................141球盒模型的概率问题摘要：利用球盒模型来研究组合恒等式，目的是寻找和证明组合恒等式，用不同的方法计算此类问题，得到不同的等式，即组合恒等式，主要内容如下：球盒模型是指n个球随机放入m个盒子的数学模型。尽管看上去这仅仅是一个普通的组合或概率问题，但里面包含着许多组合工具，如发生函数、整数分拆、Stirling数等。选择这个问题讨论对象（或情况不同），会产生许多有趣的组合结论（主要是组合恒等式），实际上包括一个组合恒等式的组合解释。因为一个等式的新的组合解释具有很高的理论与实际应用价值，以本文就是由不同的方法，把组合数学的知识与概率知识相结合得到不同的组合恒等式作为创新点。关键词：组合恒等式；发生函数；整数分拆；Stirling数；概率1绪论1.1问题的提出组合数学是研究任意一组离散性事物按照一定规则安排或配置的数学.特别是当指定的规则较简单时,计算一切可能的安排或配置的方法数,就成为它研究的主要问题.现代组合数学有两个主要特点:其一,它大量应用了抽象代数学工具和矩阵工具促使问题的提法和处理方法表现出极大的普遍性;其二,为了适应计算机科学的发展,它很注重对方法的能行性和程序化问题进行研究.组合数学最早是同数论和概率论交叉在一起的.概率方法是解决离散数学尤其是组合数学中许多问题的强有力工具。该方法在组合数学中应用大致分为两类：一类是非构造性的概率方法,该类方法从本质上讲，是一种粗糙的计数论证方法，常被用来断定具有某种特性的组合对象的存在性；一类是构造性的概率方法,该方法是用概率的语言描述一些组合对象，然后借助概率论中的方法与技巧解决组合分析的问题。非构造性概率方法就是用基本概率方法、期望的线性法在一些组合问题中的应用,如何用它们来证明一些命题和定理。构造性概率方法，即一些常见组合变量(以后统称组合数为组合变量)的概率表示,诸如Stirling数、Bell数、调和数、Fibonacci数、错排数都可以表示为一些随机变量的矩,这些概率表示可以用来研究组合和式的计算与恒等式的证明。本文主要研究了概率方法在一些重要组合数中的应用。组合数学是一门即古老又新颖的数学分支。它属于离散数学范畴，主要是研究一组离散性对象的关系，按照一定规则安排或配置方法的数学。最初是以游戏的形式出现的，由于在娱乐中和美学中有很多研究的组合问题，现在无论在纯粹或在应用科学上都有重要的价值。组合数学渗透到其它很多领域，同时其它学科方法（如概率论方法等）又为组合数学提供了新的工具。在组合数学中，组合恒等式的证明和寻找是一个很重要的内容，而组合恒等式作为计数问题的结果，所以组合数学的一个重要分支是如何证明和寻找组合恒等式。1.2研究现状组合数学在国外早已成为十分重要的学科，一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。美国一个重要的国家实验室Sandia国家实验室有一个专门研究组合数学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。日本的NEC公司还在美国的设立了研究中心，理论计算机科学和组合数学已是他们重要的研究课题。由于DNA就是组合数学中的一个序列结构，美国科学院院士，近代组合数学的奠基人Rota教授预言，生物学中的组合问题将成为组合数学的一个前沿领域。美国的大学，国家研究机构，工业界，军方和情报部门都有许2多组合数学的研究中心，在研究上投入了大量的经费。高层次的软件产品处处用到组合数学，更确切地说就是组合算法。除此之外，欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的组合数学研究中心。组合数学是计算机软件产业的基础，中国最终一定能成为一个软件大国，但是要实现这个目标的一个突破点就是发展组合数学。相对国外的发展情况，国内关于组合方法的研究和使用情况还处于相当初始的阶段。组合数学应用方面的有关文献报道是极为有限的，而在广大的生产领域几乎是空白，极少数科研单位和高校等在极个别方面有一些初步的尝试。这可能预示着在不久的将来组合技术在国内会有一个较快的发展。组合数学与概率论中的离散型随机理论密切相关，而球盒模型是用组合数学的知识解决概率论中的离散型随机问题的重要数学方法。在离散型随机理论方面，组合数学与相关的离散数学的方法占据了一个非常重要的中心位置。在这些方法中，组合列举的方法和基本的有限差分的计算方法是最主要的。尤其是，在离散型概率理论中，随机现象或随机实验被描述为是球放入盒子的随机分配模型。在本文中我们称之为n个球放入m个盒子里的球盒模型，此模型非常灵活，条件稍微变换一点，甚至是一字之差，其算法也大相径庭。所以，在不同的分配条件下，所研究的球盒模型分别与第一类、第二类Stirling数，以及发生函数、整数分拆等。各种情况相互联系，从而产生许多有趣结论。1.3研究的目的和研究的内容本文研究的目的主要是利用组合数学知识与概率的的知识相结合，从而得到组合恒等式的证明。其方法有很多，主要有组合分析法、生成函数法、矩阵方法、求导方法、概率方法、无穷级分的方法、代数方法、机器证明、超几何级数等方法，但是目前应用最为广泛的主要有以下两种方法：（1）发生函数方法1990年美国数学家Wilf出版了（GeneratingFunctionology）专著，并在专著中详细论述了发生函数各种用途，如为序列成员找出一个准确公式、寻找递归关系、求序列的平均数和其它的统计性质、根据序列发生函数的性质、找出这个序列的新信息、求序列的渐近公式、证明单峰性、凸性、证明组合恒等式等等。Wilf在书中列出很多例子说明如何利用发生函数证明组合恒等式。发生函数是解决离散数学问题的有效工具，它是离散数学和连续分析的桥梁，所以发生函数是现代离散数学领域中重要的方法之一，它能以某种统一性美妙之处已成为组合数学研究者的共识。发生函数的英文原词是generatingfunction。它的另外两个译名是生成函数与母函数。发生函数方法是现代离散数学领域中的重要方法，它能以某种统一的程序方式处理和解决众多不同类型的问题。（2）概率方法概率的概念形成于16世纪，与用投掷骰子的方法进行赌博有密切的联系。概率本来最初就是开始于赌博，由赌博发展而来的。应用概率统计方法，主要包括随机事件及其概率、随机变量及其概率分析、随机变量的数字特征及极限定理、参数估计、假设检验、方差分析、回归分析、试验设计、概率论基础与统计计算。而本文主要是把组合数学的有关知识与概率的方法结合，用概率的知识解决组合知识，用不同的方法得出不同的结论，从而得出恒等式。1.4本文主要内容本文主要是把组合数学与概率的知识相结合来研究球盒模型。所谓球盒模型，最基本的情况就是将n个球放到m个盒子里，依据球和盒子是否有区别以及是否“许空3盒而“在种23=8种状态。引入了第二类斯特灵数S2(n,m)和协同组合数mn:以及整数的分拆Pmn,等等。概率最基本的方法之一就是古典概型，而古典概型是概率论发展史上首先被人们研究的概率模型。组合数学与古典概率关系密切,利用概率来研究组合问题，证明组合恒等式是目前研究的重要方法之一。而概率论