下载文档原格式
3.计数Counting3.1排列Permutations（置换）3.1.1乘积集合Product Sets,卡氏积Cartesian Product设A,B是两个集合，元素a∈A, b∈B，称(a,b)为一个序对，或序偶ordered pair。
(a,b)=(c,d)当且仅当a=c∧b=d定义乘积集合A⨯B ={(a,b)| a∈A,b∈B }定理1 乘法原理Multiplication Priciple|A⨯B|=|A|⨯|B|假设依次实行T1,T2两种任务，如果做T1有n1种不同的办法, 做T2有n2种不同的办法, 则共有n1⨯n2种方法完成任务T1T2。
定理2 乘法原理推广|A1⨯A2⨯…⨯A k|=|A1|⨯|A2|⨯…⨯|A k|假设依次实行任务T1, T2, ……,T k,如果做T1有n1种不同的办法, 做T2有n2种不同的办法,…做T k有n k种不同的办法, 则共有n1⨯n2⨯…⨯n k种方法完成任务T1T2…T k。
例1．a) 用1，2，3，4，5可以组成多少个不同的三位数？b)用0，1，2，3，4，5可以组成多少个不同的三位数？解a) 第一位有5种取法，第二位，第三位也都有5种取法，共组成53=125个不同的三位数。
b) 第一位有5种取法，第二位，第三位有6种取法，共组成5⨯62=180个不同的三位数。
例2．n个元素的集合A共有多少个子集？解 由第一章知可以用n 个1的数组表示A, A 的子集可以用长度为n 的0，1序列表示。
每一位可以取0或1，两种取法，共有2⨯2⨯2⨯…⨯2=2n 种不同的01串，对应2n 个不同的子集。
定理3. 从n 个元素的集合A 中可重复地取出r 个元素排成一列，共有n r 种不同的取法。
定理4. 从n 个元素的集合A 中不重复地取出r 个元素排成一列，共有n(n-1)…(n-r+1)种不同的取法。
简称n 个元素中取r 个元素的排列Permuations 有r n P 种，排列rn P= n(n-1)…(n-r+1)=)!(!r n n -=[]rn全排列 从n 个元素的集合A 中不重复地取出n 个元素排成一列，共有n!种不同的取法。
《组合数学》第二讲排列组合生成算法1一. 排列生成算法z排列生成有几种典型算法, 这些算法都很有成效. 它们在实际中具有广泛应用价值.1.序数法2.字典序法3.邻位互换法(Johnson-Trotter)4.轮转法31. 序数法z序数法基于一一对应概念.z先在排列和一种特殊的序列之间建立一种一一对应关系, 然后再给出由序列产生排列的方法z因为序列的产生非常方便, 这样我们就可以得到一种利用序列来生成排列的方法.z如何建立这种一一对应?45z 思路类似数的10进制、2进制和p 进制表示.;90,1010≤≤=∑−=k m k k k a a n;10,210≤≤=∑−=k m k k k a a n.10,1−≤≤=∑−=p a p a n k m k kkz这相当于自然数与某种序列之间建立了一一对应关系.z可以利用置换来表示整数:n!=n(n-1)! =(n-1+1)(n-1)!= (n-1)(n-1)!+(n-1)!(n-1)!= (n-2)(n-2)!+(n-2)!n!= (n-1)(n-1)!+ (n-2)(n-2)!+ (n-3)(n-3)!+…+2•2!+1•1!+16z n!-1=(n-1) (n-1)!+(n-2) (n-2)!+(n-3) (n-3)!+ …+2•2!+1•1!z可以证明, 从0到n!-1之间的任何整数m 都可唯一地表示为:m=a n-1 (n-1)!+a n-2 (n-2)!+…+a2•2!+a1•1!其中0≤a≤i, i=1,2, …,n-1.iz m与序列(a n-1,a n-2 ,…a2,a1)一一对应z书中有确定这些系数的方法.z例如：10＝1⋅3!＋2⋅2!＋0⋅1!7z因为满足条件0≤a≤i, 1≤i≤n-1 （2.1）i的序列(a, a n-2, …, a2, a1)n-1共有n!个, 这恰好与0到n!-1的n!个整数一一对应.z需要建立满足条件(2.1)的n!个序列(a, a n-2, …, a2, a1)和n元集合S的n-1全部排列之间的一一对应关系.89z 还需要给出一种办法, 由每个满足条件(2.1)的序列(a n -1,a n -2, …,a 2,a 1)可生成唯一的一个排列.z 这样我们就可以产生出所有的排列. z 怎么样由一个满足条件(2.1)的序列产生一个n 阶排列?z 如何把1,2,…,n 的一个排列与一个满足条件(2.1)的序列建立起直接的关系?10z 行列式定义中有逆序数的概念, 就是一个排列中违反自然顺序的数对: 比如12354的逆序数为1, 而43215的逆序数为6.z 设p 1p 2…p n 是任意一个n 元排列, 则i +1后面比i +1小的数字的个数a i 总不超过i , 即a i ≤i , i =1,2,…,n -1.z 这样自然由一个排列得到一个序列(a n -1,a n -2,…,a 2,a 1), 而且满足条件(2.1).11z 我们可以如下建立序列与排列的对应:z 设序列(a n -1,a n -2, …,a 2,a 1)满足条件(2.1).则它所对应的排列为(p)=p 1p 2…p n , 其中a i 可以看作是排列(p)中数i +1所在位置后面比i +1小的数的个数.z 要说明这种对应的合理性, 必须清楚. 如何由序列产生出它所对应的排列.z 我们通过一个具体的例题说明思想方法.12例2.1(1) 4213→(301)4后面比4小的数的个数a 3=3; 3后面比3小的数的个数a 2=0; 2后面比2小的数的个数a 1=1.(2) (301) →4213由a 3=3知1,2,3都在4的后面; 由a 2=0知1,2都在3前面; 由a 1=1知1在2后面.(3) (4213)↔(a 3a 2a 1)=(301).2. 字典序法对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。
3.计数Counting3.1排列Permutations（置换）3.1.1乘积集合Product Sets,卡氏积Cartesian Product设A,B是两个集合，元素a∈A, b∈B，称(a,b)为一个序对，或序偶ordered pair。
(a,b)=(c,d)当且仅当a=c∧b=d定义乘积集合A⨯B ={(a,b)| a∈A,b∈B }定理1 乘法原理Multiplication Priciple|A⨯B|=|A|⨯|B|假设依次实行T1,T2两种任务，如果做T1有n1种不同的办法, 做T2有n2种不同的办法, 则共有n1⨯n2种方法完成任务T1T2。
定理2 乘法原理推广|A1⨯A2⨯…⨯A k|=|A1|⨯|A2|⨯…⨯|A k|假设依次实行任务T1, T2, ……,T k,如果做T1有n1种不同的办法, 做T2有n2种不同的办法,…做T k有n k种不同的办法, 则共有n1⨯n2⨯…⨯n k种方法完成任务T1T2…T k。
例1．a) 用1，2，3，4，5可以组成多少个不同的三位数？b)用0，1，2，3，4，5可以组成多少个不同的三位数？解a) 第一位有5种取法，第二位，第三位也都有5种取法，共组成53=125个不同的三位数。
b) 第一位有5种取法，第二位，第三位有6种取法，共组成5⨯62=180个不同的三位数。
例2．n个元素的集合A共有多少个子集？解 由第一章知可以用n 个1的数组表示A, A 的子集可以用长度为n 的0，1序列表示。
每一位可以取0或1，两种取法，共有2⨯2⨯2⨯…⨯2=2n 种不同的01串，对应2n 个不同的子集。
定理3. 从n 个元素的集合A 中可重复地取出r 个元素排成一列，共有n r 种不同的取法。
定理4. 从n 个元素的集合A 中不重复地取出r 个元素排成一列，共有n(n-1)…(n-r+1)种不同的取法。
简称n 个元素中取r 个元素的排列Permuations 有r nP 种，排列rn P= n(n-1)…(n-r+1)=)!(!r n n -=[]rn全排列 从n 个元素的集合A 中不重复地取出n 个元素排成一列，共有n!种不同的取法。
3.计数Counting3.1排列Permutations（置换）3.1.1乘积集合Product Sets,卡氏积Cartesian Product设A,B是两个集合，元素a∈A, b∈B，称(a,b)为一个序对，或序偶ordered pair。
(a,b)=(c,d)当且仅当a=c∧b=d定义乘积集合A⨯B ={(a,b)| a∈A,b∈B }定理1 乘法原理Multiplication Priciple|A⨯B|=|A|⨯|B|假设依次实行T1,T2两种任务，如果做T1有n1种不同的办法, 做T2有n2种不同的办法, 则共有n1⨯n2种方法完成任务T1T2。
定理2 乘法原理推广|A1⨯A2⨯…⨯A k|=|A1|⨯|A2|⨯…⨯|A k|假设依次实行任务T1, T2, ……,T k,如果做T1有n1种不同的办法, 做T2有n2种不同的办法,…做T k有n k种不同的办法, 则共有n1⨯n2⨯…⨯n k种方法完成任务T1T2…T k。
例1．a) 用1，2，3，4，5可以组成多少个不同的三位数？b)用0，1，2，3，4，5可以组成多少个不同的三位数？解a) 第一位有5种取法，第二位，第三位也都有5种取法，共组成53=125个不同的三位数。
b) 第一位有5种取法，第二位，第三位有6种取法，共组成5⨯62=180个不同的三位数。
例2．n个元素的集合A共有多少个子集？解 由第一章知可以用n 个1的数组表示A, A 的子集可以用长度为n 的0，1序列表示。
每一位可以取0或1，两种取法，共有2⨯2⨯2⨯…⨯2=2n 种不同的01串，对应2n 个不同的子集。
定理3. 从n 个元素的集合A 中可重复地取出r 个元素排成一列，共有n r 种不同的取法。
定理4. 从n 个元素的集合A 中不重复地取出r 个元素排成一列，共有n(n-1)…(n-r+1)种不同的取法。
简称n 个元素中取r 个元素的排列Permuations 有r n P 种，排列rn P= n(n-1)…(n-r+1)=)!(!r n n -=[]rn全排列 从n 个元素的集合A 中不重复地取出n 个元素排成一列，共有n!种不同的取法。
第四章生成排列和组合4.1 生成排列算法一: (生成集合{1,2,…,n}的n!个排列)基本思想是递归地对集合{1,2,…,n-1}的(n-1)!个排列的每一个排列, 通过把n插入到首、尾和任两个数的中间共n个位置，产生集合{1,2,…,n}的n个排列，从而产生n (n-1)!=n!个集合{1,2,…,n}的排列。
算例：排列n=1: 1n=2: 1 22 1n=3: 1 2 31 3 23 1 23 2 12 3 12 1 3n=4:1 2 3 41 2 4 31 42 34 1 2 34 1 3 21 4 3 21 3 4 21 32 43 1 2 43 14 23 4 1 24 3 1 24 3 2 13 4 2 13 24 13 2 1 42 3 1 42 3 4 12 43 14 2 3 14 2 1 32 4 1 32 1 4 32 13 4n=5:、、、算法结束，生成全部排列。
算法二: (生成集合{1,2,…,n}的n!个排列)定义:对任一给定整数k, 其上加一个箭头表示移动方向,k 或k . 对于集合{1,2,…,n}的任一个排列,其中每一个整数都有一个箭头指出其移动方向, 若整数k 的箭头指向与其相邻但比它小的整数, 称k 是活动的.算法:从1 2 3 …n 开始, 当不存在活动的整数时,算法结束.(1) 求出最大的活动整数m;(2) 交换m 和它箭头所指的相邻数;(3) 改变所有满足p>m 的整数p 的方向.算例: (n=4)4.2 排列中的逆序定义：令i 1 i 2 …i n 是集合{1,2,…,n}的一个排列，如果 0≤ k < L ≤n, 且i k >i L , 称数对（i k ，i L ）是排列的一个逆序。
例：31524的逆序定义：令a j表示排列i1 i2…i n中数j的逆序数，称a1, a2,…, a n为排列i1 i2…i n的逆序列。
例：排列31524的逆序列逆序列的性质：(1) 0≤a1≤n-1, 0≤a2≤n-2, …, 0≤a n-1≤1, a n =0。
