排列和逆序的奇偶性不同的证明

2023-11-22 理论教育版权反馈

【摘要】：cr （9.1）进行一次a，b之间的对换，得到排列a1a2…cr. （9.2）我们证明排列（9.2）与排列（9.1）的奇偶性不同.首先在排列（9.1）中将数码a依次与其右边的数码进行相邻对换，进行s次相邻对换后得到排列a1a2…

把n个自然数1，2，…，n排成一列j₁j₂…j_n，这样的一个全排列称之为一个n级排列，简称为n-排列.由初等组合数学的知识可以知道n-排列一共有n！个.在这里，我们要讨论排列的一种性质，称之为逆序.所谓逆序就是在一个排列中与自然顺序相反的顺序.

定义9.1 在一个排列中，如果一个大数排在一个小数之前，则这两个数构成该排列的一个逆序.排列j₁j₂…j_n所含有的逆序的总数称为该排列的逆序数，记作τ（j₁j₂…j_n）.

一个排列的逆序数为奇数时，称这个排列为奇排列；逆序数为偶数时，就称这个排列为偶排列.例如，3142是一个4级排列，在12、14、34之间都是自然顺序；在13、23、24之间不是自然顺序，构成逆序31、32、42，且逆序数是3，所以3142是一个奇排列.

定义9.2 在一个排列中，某两个数的位置互换，其余的数位置不动，就得到一个新排列.排列的这种变化称为排列的一个对换.

如果在某排列中进行相邻元素之间的对换，那么把大的数码换到小的数码之前，逆序增加一个；把小的数码换到大的数码之前，逆序就减少一个.从而有：

命题9.1 在排列中对换相邻两个数，改变排列的奇偶性.

定理9.1 对换改变排列的奇偶性.

证明：对排列

a₁a₂…a_tab₁b₂…b_sbc₁c₂…c_r （9.1）

进行一次a，b之间的对换，得到排列

a₁a₂…a_tbb₁b₂…b_sac₁c₂…c_r. （9.2）

我们证明排列（9.2）与排列（9.1）的奇偶性不同.

首先在排列（9.1）中将数码a依次与其右边的数码进行相邻对换，进行s次相邻对换后得到排列

a₁a₂…a_tb₁b₂…b_sabc₁c₂…c_r，（9.3）

再将排列（9.3）中的数码b依次与其左边的数码进行相邻对换，进行s+1次相邻对换后排列（9.3）变为排列（9.2）.总之排列（9.1）进行2s+1次相邻对换，就可以变为排列（9.2），由命题9.1知定理成立.证毕.(www.chuimin.cn)

推论9.1 奇排列变为自然顺序排列需经过奇数次对换，偶排列变为自然顺序排列需经过偶数次对换.

证明：只需要注意到自然顺序排列的逆序数为零，因此是偶排列.证毕.

习题

9.1.1. 计算下列排列的逆序数，并判断其奇偶性.

（1）135246；

（2）6253147；

（3）217986354；

（4）987654321.

9.1.2. 计算下列排列的逆序数，并判断其奇偶性.

（1）n（n-1）…21；

（2）24…（2n）13…（2n-1）；

（3）13…（2n-1）2n…42；

（4）（8n）（8n-1）（8n-4）（8n-5）…85412367…（8n-7）（8n-6）（8n-3）（8n-2）.

9.1.3. 如果排列x₁x₂…x_n的逆序数是k，那么排列x_n…x₂x₁的逆序数是多少？