逆序数

You are currently browsing articles tagged 逆序数.

习题2.1.1: 试通过一系列对换,将排列 {13852476} 变为排列 {72453816}.

解:{72453816=a_1a_2a_3a_4a_5a_6a_7a_8}.则排列{13852476=a_7a_5a_6a_4a_2a_3a_1a_8}.现在进行对换操作:

\displaystyle a_7a_5a_6a_4a_2a_3a_1a_8\rightarrow a_5a_7a_6a_4a_2a_3a_1a_8\rightarrow a_5a_6a_7a_4a_2a_3a_1a_8\rightarrow a_5a_6a_4a_7a_2a_3a_1a_8\rightarrow a_5a_6a_4a_2a_7a_3a_1a_8\rightarrow a_5a_6a_4a_2a_3a_7a_1a_8\rightarrow a_5a_6a_4a_2a_3a_1a_7a_8\rightarrow a_5a_4a_6a_2a_3a_1a_7a_8\rightarrow a_5a_4a_2a_6a_3a_1a_7a_8\rightarrow a_5a_4a_2a_3a_6a_1a_7a_8\rightarrow a_5a_4a_2a_3a_1a_6a_7a_8\rightarrow a_4a_5a_2a_3a_1a_6a_7a_8\rightarrow a_4a_2a_5a_3a_1a_6a_7a_8\rightarrow a_4a_2a_3a_5a_1a_6a_7a_8\rightarrow a_4a_2a_3a_1a_5a_6a_7a_8\rightarrow a_2a_4a_3a_1a_5a_6a_7a_8\rightarrow a_2a_3a_4a_1a_5a_6a_7a_8\rightarrow a_2a_3a_1a_4a_5a_6a_7a_8\rightarrow a_2a_1a_3a_4a_5a_6a_7a_8\rightarrow a_1a_2a_3a_4a_5a_6a_7a_8. \Box

习题2.1.2: 设 {1274j56k9}{1j25k4897}{9}个正整数{1,2,3,4,5,6,}{7,8,9}的排列.试决定整数{j}{k},使得前者是奇排列,后者是偶排列.

勘误: 该题目叙述有问题.在第1个排列中,{jk}只可能是{3,8}的一个排列.在第2个排列中,{jk}只可能是{3,6}的一个排列.所以题目有问题. \Box

 

习题2.1.3: 试求下列排列的奇偶性,即计算

  • {\delta_{n(n-1)\cdots ~2~1}^{1~2~\cdots (n-1)n}}.
  • {\delta_{1357\cdots (2n-1)~2~4~\cdots (2n)}^{1234\cdots ~n~(n+1)(n+2)\cdots (2n)}}.
  • {\delta_{246\cdots (2n)1~3\cdots (2n-1)}^{123\cdots n(n+1)(n+2)\cdots (2n)}}.
  • {\delta_{2143\cdots (2n)~(2n-1)}^{1234\cdots (2n-1)~(2n)}}.
  • {\delta_{369(12)\cdots (3n)1~4~7~\cdots (3n-2)~2~5~8\cdots (3n-1)}^{1234\cdots n(n+1)(n+2)(n+3)\cdots ~(2n)(2n+1)(2n+2)(2n+3)\cdots ~(3n)}}.

解:

  • {\delta_{n(n-1)\cdots ~2~1}^{1~2~\cdots (n-1)n}=(-1)^{(n-1)+(n-2)+\cdots+2+1}=(-1)^{\frac{n(n-1)}{2}}}.
  • {\delta_{1357\cdots (2n-1)~2~4~\cdots (2n)}^{1234\cdots ~n~(n+1)(n+2)\cdots (2n)}=(-1)^{1+2+\cdots+(n-1)}=(-1)^{\frac{n(n-1)}{2}}}.
  • {\delta_{246\cdots (2n)1~3\cdots (2n-1)}^{123\cdots n(n+1)(n+2)\cdots (2n)}=(-1)^{1+2+\cdots+n}=(-1)^{\frac{(n+1)n}{2}}}.
  • {\delta_{2143\cdots (2n)~(2n-1)}^{1234\cdots (2n-1)~(2n)}=(-1)^n}.
  • {\delta_{369(12)\cdots (3n)1~4~7~\cdots (3n-2)~2~5~8\cdots (3n-1)}^{1234\cdots n(n+1)(n+2)(n+3)\cdots ~(2n)(2n+1)(2n+2)(2n+3)\cdots ~(3n)}}{=(-1)^{(1+2+\cdots+n)+[1+2+\cdots+(n-1)]}=(-1)^{n^2}}.

Tags: , ,

先介绍对换的概念,该概念引自许以超《线性代数与矩阵论》(第二版)第2.1节:

定义 1 (对换) 任取一个排列{i_1i_2\cdots i_n},将其中两个相邻的正整数{i_{j-1},i_j}对换 一下,便造出一个新的排列{i_1i_2\cdots i_{j-2}i_ji_{j-1}i_{j+1}\cdots i_n},称为原来排列的对换排列.这样一种步骤称为对换.

再介绍逆序数的概念:

定义 2 (逆序数) 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序.一个排列中逆序的总数就称为这个排列的逆序数.

该书同一节的定理2.1.1叙述如下:

定理 3 如果有一种对换方式,经过作用偶(奇)数次对换,将排列{i_1i_2\cdots i_n}变为标准排列{12\cdots n},那末,不管用哪种对换方式将排列{i_1i_2\cdots i_n}变为标准排列{12\cdots n},都需要作用偶(奇)数次对换.换句话说,对换次数的奇偶性和对换方式无关.

这个定理是奇排列和偶排列概念的基石.倘若没有这个定理,奇偶排列的定义便是失败的(ill-defined).

许以超是用数学归纳法证明这个定理的.我没有耐心去看他的证明,便自己构思了一个证明.这个证明是我在2010年11月25日构思出来的,发布在自己的QQ空间里.现在重新整理在此.

证明: 首先,进行一次对换,会使排列的逆序数{+1}{-1}:进行交换的两个数,如果原来前面的数小于后面的数,则对换后排列的逆序数加{1};如果前面的数大于后面的数,则对换后逆序数{-1}.

比如排列{312}的逆序数为{2},要经过一系列对换变成排列123,可以有以下对换步骤

\displaystyle 312\rightarrow 132\rightarrow 123.

两次对换的逆序数都是{-1}的,直到变成标准排列{123},标准排列的逆序数为{0}.因此这个过程从逆序数增减的角度来看,即{2-1-1=0}.排列{312}也可以通过对换步骤

\displaystyle 312\rightarrow 321\rightarrow 231\rightarrow 213\rightarrow 123.

变成标准排列.这个过程从逆序数增减的角度来看,可以翻译为{2+1-1-1-1=0}.

一般地,设某个排列的逆序数为{p}.该排列经过{m}次对换变为标准排列,从逆序数增减的角度来看,即

\displaystyle p\cdots+1\cdots-1\cdots-1\cdots+1\cdots=0.

其中{-1}的数目比{+1}的数目多{p}个,且{+1}{-1}{m}个.无论在上式的随便一些位置加上{k}{+1},为了保持等式成立,都要在另外一些 地方地方加上{k}{-1}.同样,无论在哪些位置加上{k}{-1},都要在另外一 些地方加上相同数目的{+1}.原本只用对换{m}次就可以达到标准排列,现在要对 换{m+2k}次才可以达到标准排列.而{m}{m+2k}的奇偶性是相同的.于是定理得 证. \Box

Tags: , ,