线性代数 求逆序数题第一题：1,3……（2n-1）2,4……2n第二题：1,3……(2n-1)2n(2n-2)……2
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/19 01:24:38
线性代数 求逆序数题第一题：1,3……（2n-1）2,4……2n第二题：1,3……(2n-1)2n(2n-2)……2
线性代数 求逆序数题
第一题：1,3……（2n-1）2,4……2n
第二题：1,3……(2n-1)2n(2n-2)……2
线性代数 求逆序数题第一题：1,3……（2n-1）2,4……2n第二题：1,3……(2n-1)2n(2n-2)……2
第一题结果是n(n-1)/2
首先,前n个数都是从小到大排列的,没有逆序数对.
然后,看2,前面n个数除了1以外的n-1个数都比它大,每一个都与它组成一对逆序数对,就有n-1个；
接着,看4,前面n个数除了1和3以外的n-2个数都比它大,每一个都与它组成一对逆序数对,就有n-2个；
.
到了2n-2时,就只有2n-1比它大,有一个逆序数对.
2n 是0.
加起来就是 0+1+2+……（n-1）=n(n-1)/2
第二题结果是n(n-1)
首先,前n个数都是从小到大排列的,没有逆序数对.
然后,看2,前面2n-1个数除了1以外的2n-2个数都比它大,每一个都与它组成一对逆序数对,就有2n-2个；
接着,看4,前面2n-2个数除了1和3以外的2n-4个数都比它大,每一个都与它组成一对逆序数对,就有2n-4个；
.
到了2n-2时,有2个比它大,有2个逆序数对.
2n 是0.
加起来就是 2*【0+1+2+……（n-1）】=n(n-1)
2n排列1,3……（2n-1）2，4……2n 中
与2构成逆序的n-1个
与4构成逆序的n-2个
与6构成逆序的n-3个
...
与2n-2构成逆序的1个
共1+2+...+(n-1)=n*(n-1)/2
2n排列1,3……(2n-1)2n(2n-2)……2 中
与2n-2构成逆序的2个
与2n-4构成逆序的4个
与2...
全部展开
2n排列1,3……（2n-1）2，4……2n 中
与2构成逆序的n-1个
与4构成逆序的n-2个
与6构成逆序的n-3个
...
与2n-2构成逆序的1个
共1+2+...+(n-1)=n*(n-1)/2
2n排列1,3……(2n-1)2n(2n-2)……2 中
与2n-2构成逆序的2个
与2n-4构成逆序的4个
与2n-6构成逆序的6个
...
与2构成逆序的2n-2个
共2+4+6+...+(2n-2)=n(n-1)个
收起
2与3,5,...,(2n-1)构成逆序,共n-1个逆序,4与5,7,..,(2n-1)构成逆序,共n-2个逆序,...,依次类推,(2n-2)与(2n-1)构成1个逆序,总共(n-1)+(n-2)+...+1=n(n-1)/2个逆序.
2与3,4..,2n构成逆序,共2n-2个逆序,4与5,6,..,2n,构成逆序,也2n-4个逆序,6与7,8,..,2n,2n,2n-6构成逆序,......
全部展开
2与3,5,...,(2n-1)构成逆序,共n-1个逆序,4与5,7,..,(2n-1)构成逆序,共n-2个逆序,...,依次类推,(2n-2)与(2n-1)构成1个逆序,总共(n-1)+(n-2)+...+1=n(n-1)/2个逆序.
2与3,4..,2n构成逆序,共2n-2个逆序,4与5,6,..,2n,构成逆序,也2n-4个逆序,6与7,8,..,2n,2n,2n-6构成逆序,...,依次类推,2n-1,2n-2与2n构成构成逆序,共2个逆序,总共(2n-2)+(2n-4)+...+2=n(n-1)个逆序.
收起