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