下载文档原格式
离散数学组合计数
离散数学中的组合计数是指研究一定范围内的元素选取，计算选
取方式总数的方法。
它主要包括排列、组合、二项式定理、斯特林数、欧拉数、生成函数等内容。
其中，排列是指从一组元素中选取若干个不同的元素，然后按一
定的顺序排列的方法数；组合是指从一组元素中选取若干个不同的元素，不考虑其顺序的选取方式总数。
二项式定理是组合计数中的基本
公式，它描述了任意两个数的幂与二项式系数之间的关系。
斯特林数
和欧拉数则是描述排列和组合问题中的一些性质和规律的重要工具，
而生成函数则是描述组合计数问题的一种通用方法。
组合计数在离散数学中起着重要的作用，它不仅在数学理论研究
中具有广泛的应用，还在计算机科学、统计学、物理学等学科中发挥
着重要的作用。
离散数学计数定律离散数学是指研究离散化对象及其性质的数学分支。
计数是离散数学的一个重要领域，涉及了各种计算和统计问题。
在离散数学计数定律中，有一些重要的原理和定理被广泛应用于计算和统计的各个领域。
1. 乘法规则：若一个计算过程分为k个相互独立的部分，且第一部分有n1种不同的方式，第二部分有n2种不同的方式，以此类推，第k部分有nk种不同的方式，则整个计算过程有n1*n2*...*nk种不同的方式。
2. 加法规则：若一个计算过程分为k个不相交的部分，且第一部分有n1种不同的方式，第二部分有n2种不同的方式，以此类推，第k部分有nk种不同的方式，则整个计算过程有n1+n2+...+nk种不同的方式。
3. 排列：从n个元素中选取r个元素进行排列，有P(n,r) = n! / (n-r)! 种不同的排列方式。
4. 组合：从n个元素中选取r个元素进行组合，有C(n,r) = n! / (r! * (n-r)!) 种不同的组合方式。
5. 二项式定理：对于任意实数a和b，以及任意非负整数n，有(a+b)^n =C(n,0)*a^n*b^0 + C(n,1)*a^(n-1)*b^1 + ... + C(n,n)*a^0*b^n。
6. 完全排列原理：对于一个元素集合S，若n个元素有ni种不同的排列方式（i从1到k），则这些元素的完全排列方式共有n1! * n2! * ... * nk! 种。
7. 抽屉原理：若n+1个物体放入n个抽屉中，至少有一个抽屉中会放有两个或更多物体。
8. 鸽笼原理：若将n+1只鸽子放入n个鸽笼中，那么至少会有一个鸽笼中放有两只或更多的鸽子。
这些离散数学计数定律在不同领域的计算和统计问题中起着重要的作用，能够帮助解决各种复杂的计数和排列组合问题。
第3章 组合论基础------计数组合论(combinatorial mathematics)是数学的一个分支，主要研究在给定模式下的可能配置，配置的存在性，配置的数目，配置的性质等等。
我们已经介绍过的鸽笼原理常被列入组合数学范畴，它被用于可能配置的存在性讨论。
计数（computing ）是组合数学领域的重要课题，其主要任务是上述配置数目的计算技术的研究。
高中阶段数学课程中的排列、组合及二项式定理等教学内容，皆属于计数这一范畴。
计数技术广泛应用于概率统计理论，以及计算机算法复杂性研究等领域。
3.1 计数基本原理计数基本原理包括加法原理和乘法原理，是高中阶段数学课程中的学习内容，我们只作简要回顾。
3.1.1 加法原理和乘法原理加法原理：若事件的有限集合n S S S ⋃⋃= 1，且n S S ,,1 两两不相交，那么 n S S S ++= 1也就是说，如果事件集合S 可以分为两两不相交的子集S 1,…,S n ，那么要对S 中事件计数时，可对子集S 1,…,S n 分别计数，然后相加来求得。
加法原理的另一个说法是：n 个独立事件分别有a 1，…，a n 种方式发生，那么这n 个事件之一发生的方式总计为a 1+ … +a n 种。
乘法原理：若事件的有限集合S 是依次取自有限集合n S S ,,1 中事件的序列的集合，那么表示数的乘法）***=(1n S S S 也就是说，如果集合S 中的事件，是由集合S 1,…,S n 中事件相继发生而形成的事件序列所构成，且S i 中每一事件的发生，可以导致S i+1中所有事件的发生（i = 1 ,2 , … ，n – 1）。
那么，对S 中的事件序列计数时，可对集合S 1,…,S n 分别计数，然后相乘来求得。
乘法原理的另一个说法是：n 个独立事件分别有a 1，…，a n 种方式发生，那么这n 个事件同时发生的方式总计为a 1*…*a n 种。
两个原理的正确性都是十分明白的。
