下载文档原格式
离散数学排列组合公式简介离散数学是一门研究离散对象的数学学科，其中排列组合是其重要的一部分。
排列组合是指在给定的元素集合中，通过选择和安排元素，得到不同的结果。
在离散数学中，排列和组合是两个基本概念，并且有相应的计算公式来帮助解决问题。
一、排列公式排列是指从给定的元素集合中，按照一定的顺序，选取若干元素进行排列。
在离散数学中，排列的计算方法有两种：允许重复和不允许重复。
下面分别介绍这两种排列的计算公式。
1. 允许重复的排列当元素集合中的元素可以重复出现在排列中时，就称为允许重复的排列。
对于含有n个元素的集合，要求选择r个元素进行排列，公式如下：P(n, r) = n^r其中，P表示排列的个数，n表示元素集合中的元素个数，r表示选择的元素个数。
举个例子，假设有一个字母集合{a, b, c}，要选择两个字母进行排列，那么根据公式，可以计算出排列的个数为：P(3, 2) = 3^2 = 9因此，共有9种不同的排列方式：aa、ab、ac、ba、bb、bc、ca、cb、cc。
2. 不允许重复的排列当元素集合中的元素不允许重复出现在排列中时，就称为不允许重复的排列。
对于含有n个元素的集合，要求选择r个元素进行排列，公式如下：P(n, r) = n! / (n - r)!其中，"!"表示阶乘，n!表示n的阶乘，即n × (n-1) × ... × 1。
举个例子，假设有一个字母集合{a, b, c}，要选择两个字母进行排列，那么根据公式，可以计算出排列的个数为：P(3, 2) = 3! / (3 - 2)! = 3! / 1! = 6因此，共有6种不同的排列方式：ab、ac、ba、bc、ca、cb。
二、组合公式组合是指从给定的元素集合中，不考虑顺序，选择若干元素进行组合。
在离散数学中，组合的计算方法也有两种：允许重复和不允许重复。
下面分别介绍这两种组合的计算公式。
离散数学集合与关系离散数学是数学中一门独立的分支，它主要研究离散的数学结构和被限制在有限范围的对象。
集合论和关系理论是离散数学的重要组成部分，它们在计算机科学、信息科学等领域具有广泛的应用。
一、集合的概念与基本运算集合是离散数学中最基本的概念之一，它是由确定的元素所组成的整体。
集合的表示通常使用大写字母，元素用小写字母表示，并用花括号{}括起来。
例如，集合A={1,2,3,4}表示由元素1,2,3,4组成的集合A。
在集合论中，集合之间的关系可以通过特定的运算来描述。
常见的集合运算包括并集、交集、差集和补集。
并集是指所有属于被操作的集合的元素的集合。
交集是指同时属于所有被操作的集合的元素的集合。
差集是指属于一个集合而不属于另一个集合的元素的集合。
补集是指在全集中属于一个集合而不属于另一个集合的元素的集合。
二、关系的定义与性质关系是描述集合之间元素之间的某种联系或者规律的数学概念。
在离散数学中，关系可以用二元组的形式表示。
关系的性质包括自反性、对称性和传递性。
自反性是指元素与自身之间存在关系。
对称性是指如果两个元素之间存在关系，那么它们之间的关系是互逆的。
传递性是指如果两个元素之间存在关系，并且与另一元素之间也存在关系，那么这两个元素之间也存在关系。
三、集合的基数与幂集集合的基数是指集合中的元素个数。
若集合A中的元素个数为n，则记作|A|=n。
基数为有限值的集合称为有限集，基数为无限值的集合称为无限集。
幂集是指一个集合的所有子集所组成的集合。
例如，对于集合A={1,2}，它的幂集为{{},{1},{2},{1,2}}。
幂集的基数等于原集合的基数的2的幂次方。
四、关系的类型与性质在离散数学中，关系可以分为几种不同的类型。
常见的关系类型包括等价关系、序关系和函数关系。
等价关系是指满足自反性、对称性和传递性的关系。
序关系是指满足自反性、反对称性和传递性的关系。
函数关系是指每个定义域中的元素都有唯一对应的值域中的元素的关系。
Author ：ssjs
Mail ：
看了离散数学中的关系整理了一点关于n 元集合中各种关系的计算，现写下这个方便大家学习交流理解。
对文章所致一切后果不负任何责任，请谨慎使用。
如有错误之处请指正。
定义：
1，对称：对于a,b R a b ∈∈∈),b (),a (,A 有如果只要
2，反对称：如果R a b R b a b b ∈∈=∈),(),(a ,A ,a 和时仅当
3，自反：如果对每个元素R ),(A a ∈∈a a 有
4，反自反：如果对于每个R ),(A a ∉∈a a 有
5，传递：如果对R ),(,R ),(R ),(,A ,,∈∈∈∈c a c b b a c b a 则且
6，非对称：如果R ),(R ),(∉∈a b b a 推出【注】其中是含（a,a)这样的有序对的。
【重要】集合A 的关系是从A 到A 的关系 （也就是说集合A 的关系是A A ⨯的子集）。
如下结论：
N 元集合上的自反关系数为：)1(2
-n n N 元集合上的对称关系数为：2/)1(2+n n
N 元集合上的反对称关系数为：2/)1(n 3
2-n n N 元集合上的非对称关系数为：2/)1(3-n n
N 元集合上的反自反关系数为：)1(n 2-n
N 元集合上的自反和对称关系数为：2/)1(n 2-n
N 元集合上的不自反也不反自反关系数为：)1(n n 222
2-⋅-n
下面是上面结论的计算
1，自反 2A A ,A n n =⨯=因为也就是说集合A 有n 平方个有序对，由自反定义可知，对R ),(A a ∈∈∀a a 有所以n 个有序对()).....3,2,1i X ,X (n i i =其中一定在所求关系中，否则的话此关系就不是自反的了，那么还有n n -2个有序对，所以由集合子集对应二进制串可得自反关系数为)1(n 222--=n n n
下图有助于理解。
（1,1) (2,2).......(n,n) | (1,2) (1,3).........(n-1,n)
N n n -2
个有序对
2，对称 2A A ,A n n =⨯=因为也就是说集合A 有n 平方个有序对，由对称定义可知，对于R a b b ∈∈∈),b (),a (,A ,a 有只要。
另外知道在n 平方个有序对中有n 个有序对()).....3,2,1i X ,X (n i i =其中，相应的就有n n -2
个有序对（X,Y)且X Y ≠，定义可知后面的n n -2个有序对只能成对出现，所以有2/)(n 2n -对。
前面的那n 对可以出现任意多对。
图片如下。
（1,1) (2,2).......(n,n) (1,2) (1,3).........(n-1,n)
n (2,1) (3,1).........(n,n-1)
(n n -2)/2个有序对对
共有n+ (n n -2)/2 个元素
即 (n n +2)/2个
所以得到对称关系数为：2/)1(2+n n
3，反自反
2A A ,A n n =⨯=因为也就是说集合A 有n 平方个有序对，由对称定义可知，如果对于每个R ),(A a ∉∈a a 有，构成该关系的元素个数为n n -2个，所以得出结论)1(n 2-n ，这个简单，不多说。
4，自反和对称
即是求自反的又对称的，由1知要是自反的就只能在n n -2个有序对中生成子集，又由对称定义可知，将n n -2个有序对分成形如(a,b)与(b,a)的(n n -2)/2个有序对对。
所以有自反和对称关系数为：2/)1(n 2-n 。
如下图
（1,1) (2,2).......(n,n) (1,2) (1,3).........(n-1,n)
n 个有序对 (2,1) (3,1).........(n,n-1)
要自反这n 个必在所求关系中
(n n -2)/2个有序对对
N 个有序对只有1种可能· 有2/)1(n 2-n 种可能 = 2/)1(n 21-⨯n
5，不自反也不反自反
不自反也不反自反 = 不自反I 不反自反
= ）不反自反不自反（Y -2n 2
= 反自反）（自反Y -2n 2
= )22(2)1()1(n 2--+-n n n n
= )1(n 2222-⋅-n n
6，非对称
由定义：如果R ),(R ),(∉∈a b b a 推出，很清楚形如(a,a)的有序对不在所求关系中。
所以所求关系只能中剩下的n n -2个有序对中来生成。
如下图。
（1,1) (2,2).......(n,n) (1,2) (1,3)...................................(n-1,n)
n (2,1) (3,1)....................................(n,n-1)
这n 个一定不在所求关系中 (n n -2 )/2个有序对对
由定义上图的同色对中只能取一个或是一个也不取，就有三种状态1）选上面的 2）选下面的 3）两个都不选
选取同色对？
0 1
不选 选上还是选下？
0 1
选上 选下
由题知，不选，选上，选下是三种互斥结果。
同集合二进制求集合个数原理，可得集合子集个为：2/)1(3-n n
7，反对称
由定义：如果R a b R b a b b ∈∈=∈),(),(a ,A ,a 和时仅当 如下图。
（1,1) (2,2)......................(n,n) (1,2) (1,3)...................................(n-1,n)
n (2,1) (3,1)...................................(n,n-1)
这n 个有序对可以出现任意多次 (n n -2 )/2个有序对对
n 2 ⨯ 2/)1(3-n n (由6可知）
所以得结果 ：n 2⨯2/)1(3-n n 即2/)1(n 32-n n
【注】其它组合或是要求可由定义同理推出。
不要怕麻烦，其实不那么难，也还有许多方法可以导出结果，如矩阵之类的。
强烈推荐看下Discrete Mathematics and Its Applications Seventh Edition 更新版的更好哈，讲得真的很不错。
参考资料：Discrete Mathematics and Its Applications SeventhEdition。
