全排列和对换.ppt

《全排列和对换.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2全排列和对换问题：把n个不同的元素排成一列，共有多少种不同的排法？定义：把n个不同的元素排成一列，叫做这n个元素的全排列．n个不同元素的所有排列的种数，通常用Pn表示．显然即n个不同的元素一共有n!种不同的排法．所有6种不同的排法中，只有一种排法（123）的数字是按照从小到大的自然顺序排列的，而其它排列中都有大的数排在小的数之前．因此大部分的排列都不是“顺序”，而是“逆序”．3个不同的元素一共有3!=6种不同的排法123，132，213，231，312，321对于n个不同的元素，可规定各元素之间的标准次序．n个不同的自然数，规定从小到大

2、为标准次序．定义：当某两个元素的先后次序与标准次序不同时，就称这两个元素组成一个逆序．例如：在排列32514中，32514逆序逆序逆序思考题：还能找到其它逆序吗？答：2和1，3和1也构成逆序．定义：排列中所有逆序的总数称为此排列的逆序数．排列i1i2…in的逆序数通常记为t(i1i2…in)．奇排列：逆序数为奇数的排列．偶排列：逆序数为偶数的排列．思考题：符合标准次序的排列是奇排列还是偶排列？答：符合标准次序的排列（例如：123）的逆序数等于零，因而是偶排列．例：求排列32514的逆序数．解：练习：求排列453162的逆序数．解：计算排列的

3、逆序数的方法（课本P.4）则此排列的逆序数为设p1p2…pn是1,2,…,n这n个自然数的任一排列，并规定由小到大为标准次序．先看有多少个比p1大的数排在p1前面，记为t1；再看有多少个比p2大的数排在p2前面，记为t2；……最后看有多少个比pn大的数排在pn前面，记为tn；二、对换的定义定义：在排列中，将任意两个元素对调，其余的元素不动，这种作出新排列的手续叫做对换．将相邻两个元素对换，叫做相邻对换．例如：备注相邻对换是对换的特殊情形．一般的对换可以通过一系列的相邻对换来实现．如果连续施行两次相同的对换，那么排列就还原了．m次相邻对换m+

4、1次相邻对换m次相邻对换m+1次相邻对换对换与排列奇偶性的关系定理1：对换改变排列的奇偶性．证明：先考虑相邻对换的情形．注意到除外，其它元素的逆序数不改变．当时，，，．当时，，，．因此相邻对换改变排列的奇偶性．既然相邻对换改变排列的奇偶性，那么2m+1次相邻对换因此，一个排列中的任意两个元素对换，排列的奇偶性改变.推论奇排列变成标准排列的对换次数为奇数，偶排列变成标准排列的对换次数为偶数．证明：由定理1知，对换的次数就是排列奇偶性的变化次数，而标准排列是偶排列(逆序数为零)，因此推论成立．