早教吧作业答案频道 -->数学-->
在数字1,2,…,n(n≥2)的任意一个排列A:a1,a2,…,an中,如果对于i,j∈N*,i<j,有ai>aj,那么就称(ai,aj)为一个逆序对.记排列A中逆序对的个数为S(A).如n=4时,在排列B:3
题目详情
在数字1,2,…,n(n≥2)的任意一个排列A:a1,a2,…,an中,如果对于i,j∈N*,i<j,有ai>aj,那么就称(ai,aj)为一个逆序对.记排列A中逆序对的个数为S(A).
如n=4时,在排列B:3,2,4,1中,逆序对有(3,2),(3,1),(2,1),(4,1),则S(B)=4.
(Ⅰ)设排列 C:3,5,6,4,1,2,写出S(C)的值;
(Ⅱ)对于数字1,2,…,n的一切排列A,求所有S(A)的算术平均值;
(Ⅲ)如果把排列A:a1,a2,…,an中两个数字ai,aj(i<j)交换位置,而其余数字的位置保持不变,那么就得到一个新的排列A':b1,b2,…,bn,求证:S(A)+S(A')为奇数.
如n=4时,在排列B:3,2,4,1中,逆序对有(3,2),(3,1),(2,1),(4,1),则S(B)=4.
(Ⅰ)设排列 C:3,5,6,4,1,2,写出S(C)的值;
(Ⅱ)对于数字1,2,…,n的一切排列A,求所有S(A)的算术平均值;
(Ⅲ)如果把排列A:a1,a2,…,an中两个数字ai,aj(i<j)交换位置,而其余数字的位置保持不变,那么就得到一个新的排列A':b1,b2,…,bn,求证:S(A)+S(A')为奇数.
▼优质解答
答案和解析
(Ⅰ)逆序对有(3,1),(3,2),(5,4),(5,1),(5,2),(4,1),(4,2),
(6,4),(6,1),(6,2)则S(C)=10;
(Ⅱ)考察排列D:d1,d2,…,dn-1,dn与排列D1:dn,dn-1,…,d2,d1,
因为数对(di,dj)与(dj,di)中必有一个为逆序对(其中1≤i且排列D中数对(di,dj)共有
=
个,
所以S(D)+S(D1)=
.
所以排列D与D1的逆序对的个数的算术平均值为
.
而对于数字1,2,…,n的任意一个排列A:a1,a2,…,an,
都可以构造排列A1:an,an-1,…,a2,a1,
且这两个排列的逆序对的个数的算术平均值为
.
所以所有S(A)的算术平均值为
.
(Ⅲ)证明:(1)当j=i+1,即ai,aj相邻时,
不妨设ai<ai+1,则排列A'为a1,a2,…,ai-1,ai+1,ai,ai+2,…,an,
此时排列A'与排列A:a1,a2,…,an相比,仅多了一个逆序对(ai+1,ai),
所以S(A')=S(A)+1,
所以S(A)+S(A')=2S(A)+1为奇数.
(2)当j≠i+1,即ai,aj不相邻时,
假设ai,aj之间有m个数字,记排列A:a1,a2,…,ai,k1,k2,…km,aj,…,an,
先将ai向右移动一个位置,得到排列A1:a1,a2,…,ai-1,k1,ai,k2,…,km,aj,…,an,
由(1)知S(A1)与S(A)的奇偶性不同,
再将ai向右移动一个位置,得到排列A2:a1,a2,…,ai-1,k1,k2,ai,k3,…,km,aj,…,an,
由(1)知S(A2)与S(A1)的奇偶性不同,
以此类推,ai共向右移动m次,得到排列Am:a1,a2,…,k1,k2,…,km,ai,aj,…,an,
再将aj向左移动一个位置,得到排列Am+1:a1,a2,…,ai-1,k1,…,km,aj,ai,…,an,
以此类推,aj共向左移动m+1次,得到排列A2m+1:a1,a2,…,aj,k1,…,km,ai,…,an,
即为排列A',
由(1)可知仅有相邻两数的位置发生变化时,排列的逆序对个数的奇偶性发生变化,
而排列A经过2m+1次的前后两数交换位置,可以得到排列A',
所以排列A与排列A'的逆序数的奇偶性不同,
所以S(A)+S(A')为奇数.
综上,得S(A)+S(A')为奇数.
(6,4),(6,1),(6,2)则S(C)=10;
(Ⅱ)考察排列D:d1,d2,…,dn-1,dn与排列D1:dn,dn-1,…,d2,d1,
因为数对(di,dj)与(dj,di)中必有一个为逆序对(其中1≤i
C | 2 n |
n(n-1) |
2 |
所以S(D)+S(D1)=
n(n-1) |
2 |
所以排列D与D1的逆序对的个数的算术平均值为
n(n-1) |
4 |
而对于数字1,2,…,n的任意一个排列A:a1,a2,…,an,
都可以构造排列A1:an,an-1,…,a2,a1,
且这两个排列的逆序对的个数的算术平均值为
n(n-1) |
4 |
所以所有S(A)的算术平均值为
n(n-1) |
4 |
(Ⅲ)证明:(1)当j=i+1,即ai,aj相邻时,
不妨设ai<ai+1,则排列A'为a1,a2,…,ai-1,ai+1,ai,ai+2,…,an,
此时排列A'与排列A:a1,a2,…,an相比,仅多了一个逆序对(ai+1,ai),
所以S(A')=S(A)+1,
所以S(A)+S(A')=2S(A)+1为奇数.
(2)当j≠i+1,即ai,aj不相邻时,
假设ai,aj之间有m个数字,记排列A:a1,a2,…,ai,k1,k2,…km,aj,…,an,
先将ai向右移动一个位置,得到排列A1:a1,a2,…,ai-1,k1,ai,k2,…,km,aj,…,an,
由(1)知S(A1)与S(A)的奇偶性不同,
再将ai向右移动一个位置,得到排列A2:a1,a2,…,ai-1,k1,k2,ai,k3,…,km,aj,…,an,
由(1)知S(A2)与S(A1)的奇偶性不同,
以此类推,ai共向右移动m次,得到排列Am:a1,a2,…,k1,k2,…,km,ai,aj,…,an,
再将aj向左移动一个位置,得到排列Am+1:a1,a2,…,ai-1,k1,…,km,aj,ai,…,an,
以此类推,aj共向左移动m+1次,得到排列A2m+1:a1,a2,…,aj,k1,…,km,ai,…,an,
即为排列A',
由(1)可知仅有相邻两数的位置发生变化时,排列的逆序对个数的奇偶性发生变化,
而排列A经过2m+1次的前后两数交换位置,可以得到排列A',
所以排列A与排列A'的逆序数的奇偶性不同,
所以S(A)+S(A')为奇数.
综上,得S(A)+S(A')为奇数.
看了 在数字1,2,…,n(n≥2...的网友还看了以下:
设|A|是三阶矩阵,A=(a1,a2,a3)则|A|=?A.|a1-a2,a2-a3,a3-a1| 2020-05-16 …
设数列[an}的前n项和为Sn,a1=a ,a2=p(p>0),Sn=n(an-a1)/2(1)求 2020-05-16 …
已知an=xa(n-1)+ya(n-2),a1=a,a2=b求通项an求和Sn把答案弄出来 2020-05-17 …
1.类比等差数列的定义,给出等和数列的定义2.探究等和数列{an}的奇数项与偶数项各有什么特点,并 2020-05-20 …
有数字a1、a2、a3、a4.an,按一定顺序排列后与之前数字完全不对应,即a1不对应a1.an不 2020-06-23 …
初二整式乘法已知从小到大排列的2014个数:a1.a2.a3⋯a2013.a2014.设M=(a1 2020-06-24 …
已知数列{an}有a1=a,a2=p(常数p>0),对任意的正整数n,Sn=a1+a2+...已知 2020-07-31 …
方程组:2a1-a2+3a3+2a4=0-a1+2a2-a3-a4=03a1+2a2+2a3+3a 2020-08-02 …
若集合A1,A2满足A1∪A2=A,则称(A1,A2)为集合的分拆,求集合A={a,b,c}的不同种 2020-11-08 …
将1,2,3,…,n这n个数随机排成一列,得到的一列数a1,a2,…,an称为1,2,3,…,n的一 2020-12-15 …