1.2 全排列和对换
18
本章目录 · 1 节
本章导读
【一、排列及其逆序数】将个互不相同的元素排成一行,称为全排列。元素取时,所有排列组成。第一位置有种选择,第二位置有种,依次相乘,得到。
例如有六个排列:。先固定由小到大为标准顺序;某对元素的先后与标准顺序相反,就构成一个逆序。逆序数是所有这样的数对的个数:
计算时可对每个元素数“前面比它大的数”,再相加;也可数“后面比它小的数”,两种方法等价,不能同时相加而重复计算。逆序数为偶数称偶排列,为奇数称奇排列;标准排列的逆序数为0,属于偶排列。
【例4】排列中,依次统计各元素前面比它大的数,得到,总数为5。因此是奇排列,其符号为。(例完)
【二、对换】交换排列中的任意两个元素,其余元素不动,称为一次对换;交换相邻元素称相邻对换。一次对换总会改变排列的奇偶性。
证明:相邻的交换时,与其他元素形成的逆序总数不变,只有这一对的逆序状态改变,故逆序数增减1。若之间隔着个元素,可用次相邻对换完成交换,因此一般对换也改变奇偶性。
【推论及解释】任意排列均能经有限次对换化为标准排列。将奇排列化为标准排列,所用对换次数必为奇数;偶排列所用次数必为偶数。具体路径可能不同,对换次数本身不必等于逆序数,但它们的奇偶性相同。这个结论使排列的符号不依赖具体排序路径。
