全排列和对换PPT学习教案

1、会计学1全排列和对换全排列和对换问题：问题：把把 n 个不同的元素排成一列，共有多少种不同的排法？个不同的元素排成一列，共有多少种不同的排法？定义：定义：把把 n 个不同的元素排成一列，叫做这个不同的元素排成一列，叫做这 n 个元素的个元素的全排列全排列n 个不同元素的所有排列的种数，通常用个不同元素的所有排列的种数，通常用Pn 表示表示(1) (2)3 2 1!nPnnnn 显然显然 即即 n 个不同的元素一共有个不同的元素一共有 n! 种不同的排法种不同的排法第1页/共13页所有所有6种不同的排法中，只有一种排法（种不同的排法中，只有一种排法（123）的数字是按照从小到大的自然顺序排列的，

2、的数字是按照从小到大的自然顺序排列的，而其它排列中都有大的数排在小的数之前而其它排列中都有大的数排在小的数之前因此大部分的排列都不是因此大部分的排列都不是“顺序顺序”，而是，而是“逆序逆序” 3个不同的元素一共有个不同的元素一共有 3! =6 种不同的排法种不同的排法123，132，213，231，312，321第2页/共13页对于对于 n 个不同的元素，可规定各元素之间的标准次序个不同的元素，可规定各元素之间的标准次序n 个不同的自然数，规定从小到大为标准次序个不同的自然数，规定从小到大为标准次序定义：定义：当某两个元素的先后次序与标准次序不同时，就当某两个元素的先后次序与标准次序不同时，就

3、称称这两个元素组成一个这两个元素组成一个逆序逆序例如：在排列例如：在排列32514中，中，3 2 5 1 4逆序逆序 逆序逆序 逆序逆序 思考题：思考题：还能找到其它逆序吗？还能找到其它逆序吗？答：答：2和和1，3和和1也构成逆序也构成逆序第3页/共13页定义定义：排列中所有逆序的总数称为此排列的排列中所有逆序的总数称为此排列的逆序数逆序数排列排列 i1i2 in 的逆序数通常记为的逆序数通常记为 t ( i1i2in ) 奇排列：奇排列：逆序数为奇数的排列逆序数为奇数的排列偶排列：偶排列：逆序数为偶数的排列逆序数为偶数的排列思考题：思考题：符合标准次序的排列是奇排列还是偶排列？符合标准次序的

4、排列是奇排列还是偶排列？ 答：答：符合标准次序的排列（例如：符合标准次序的排列（例如：123）的逆序数等于零，因）的逆序数等于零，因而是偶排列而是偶排列第4页/共13页例：例：求排列求排列 32514 的逆序数的逆序数解：解：(32514)010315t 练习：练习：求排列求排列 453162 的逆序数的逆序数9t 解：解：第5页/共13页计算排列的逆序数的方法计算排列的逆序数的方法（课本（课本P.4）则此排列的逆序数为则此排列的逆序数为12ntttt设设 p1p2 pn 是是 1, 2, , n 这这 n 个自然数的任一排列，并个自然数的任一排列，并规定由小到大为标准次序规定由小到大为标准次

5、序先看有多少个比先看有多少个比 p1大的数排在大的数排在 p1前面，记为前面，记为 t1 ；再看有多少个比再看有多少个比 p2大的数排在大的数排在 p2前面，记为前面，记为 t2 ；最后看有多少个比最后看有多少个比 pn大的数排在大的数排在 pn前面，记为前面，记为 tn ；第6页/共13页111lmnaabbcb ca定义：定义： 在排列中，将任意两个元素对调，其余的元素在排列中，将任意两个元素对调，其余的元素不动，这种作出新排列的手续叫做不动，这种作出新排列的手续叫做对换对换将相邻两个元素对换，叫做将相邻两个元素对换，叫做相邻对换相邻对换例如：例如： 11lma baabb11lmb aa

6、abb111lmnaabbca cb第7页/共13页备注备注1.相邻对换是对换的特殊情形相邻对换是对换的特殊情形2.一般的对换可以通过一系列的相邻对换来实现一般的对换可以通过一系列的相邻对换来实现3.如果连续施行两次相同的对换，那么排列就还原了如果连续施行两次相同的对换，那么排列就还原了m 次相邻对换次相邻对换 111lmnaabbcb ca111 lmnaabbcbca111 lmnaabbca cbm+1次相邻对换次相邻对换 m 次相邻对换次相邻对换 111 lmnaabbcacb111 lmnaabbcb cam+1次相邻对换次相邻对换 第8页/共13页定理定理1：对换改变排列的奇偶性对

7、换改变排列的奇偶性证明：证明：先考虑相邻对换的情形先考虑相邻对换的情形11 lma baabb11 lmb aaabb11lmabaabbttttttt 11lmbaaabbrrtttrt 第9页/共13页11 lma baabb11 lmb aaabb11lmabaabbttttttt 11lmbaaabbrrtttrt 注意到除注意到除 外，其它元素的逆序数不改变外，其它元素的逆序数不改变,a b()()()()ababaabbrrttrtrtrt 第10页/共13页11 lma baabb11 lmb aaabb11lmabaabbttttttt 11lmbaaabbrrtttrt 当当

8、 时，时， ， ， ab 当当 时，时， ， ， ab 因此相邻对换改变排列的奇偶性因此相邻对换改变排列的奇偶性1aartbbrt aart 1bbrt1rt 1rt ()()()()ababaabbrrttrtrtrt 第11页/共13页既然相邻对换改变排列的奇偶性，那么既然相邻对换改变排列的奇偶性，那么 2m+1次相邻对换次相邻对换因此，一个排列中的任意两个元素对换，排列的奇偶性改变因此，一个排列中的任意两个元素对换，排列的奇偶性改变.111lmnaabbcb ca111 lmnaabbca cb推论推论 奇排列奇排列变成标准排列的对换次数为变成标准排列的对换次数为奇数奇数， 偶排列偶排列变成标准排列的对