求教数学题,具体问题看补充
我们考虑一个由{1,2,……,n,……,2n}这2n个正整数组成的长度为2n的数字序列A。如果i>j而且A[i]>A[j]则称A中的i和j构成了一个“逆序对”。显然,序列...
我们考虑一个由{1,2,……,n,……,2n}这2n个正整数组成的长度为2n的数字序列A。如果i>j而且A[i]>A[j]则称A中的i和j构成了一个“逆序对”。显然,序列A中的任意两个位置都有可能成为逆序对。例如,一个完全正序的序列:1,2,3,……,2n中没有逆序对。而完全逆序的序列2n,2n-1,……,3,2,1中逆序对的个数是(4n-1)*2n个。
我们既不考虑完全正序序列,也不考虑完全逆序序列。我们讨论一类特殊的“半序序列”:一个任意的排列A=(a[1],a[2],…,a[n],…,a[2n]),如果所有奇数位置上的数都正序排列,则称之为一个半序序列,例如:
1 2 3 4 5 6 7 8 9 10
3 2 4 10 6 7 8 1 9 5
例如以下序列就不是半序序列:
10 9 8 7 6 5 4 3 2 1 (所有位置都不是正序)
10 1 9 2 3 4 5 6 7 8(10和9都在奇数位置上,而且他们顺序反了)
我们想知道某种长度的半序序列的逆序对的平均个数。例如,n=2时,半序序列有12个:
1 2 3 4 (逆序对0个)
1 2 4 3 (逆序对1个)
1 3 2 4 (逆序对1个)
1 3 4 2 (逆序对2个)
1 4 2 3 (逆序对2个)
1 4 3 2 (逆序对3个)
2 1 3 4 (逆序对1个)
2 1 4 3 (逆序对2个)
2 3 4 1 (逆序对3个)
2 4 3 1 (逆序对4个)
3 1 4 2 (逆序对3个)
3 2 4 1 (逆序对4个)
所以,平均逆序对个数是:26/12个。
现给出计算的公式。 展开
我们既不考虑完全正序序列,也不考虑完全逆序序列。我们讨论一类特殊的“半序序列”:一个任意的排列A=(a[1],a[2],…,a[n],…,a[2n]),如果所有奇数位置上的数都正序排列,则称之为一个半序序列,例如:
1 2 3 4 5 6 7 8 9 10
3 2 4 10 6 7 8 1 9 5
例如以下序列就不是半序序列:
10 9 8 7 6 5 4 3 2 1 (所有位置都不是正序)
10 1 9 2 3 4 5 6 7 8(10和9都在奇数位置上,而且他们顺序反了)
我们想知道某种长度的半序序列的逆序对的平均个数。例如,n=2时,半序序列有12个:
1 2 3 4 (逆序对0个)
1 2 4 3 (逆序对1个)
1 3 2 4 (逆序对1个)
1 3 4 2 (逆序对2个)
1 4 2 3 (逆序对2个)
1 4 3 2 (逆序对3个)
2 1 3 4 (逆序对1个)
2 1 4 3 (逆序对2个)
2 3 4 1 (逆序对3个)
2 4 3 1 (逆序对4个)
3 1 4 2 (逆序对3个)
3 2 4 1 (逆序对4个)
所以,平均逆序对个数是:26/12个。
现给出计算的公式。 展开
展开全部
我们可以设n个元素为1至n这n个自然数,并规定由大到小为标准次序。设p1p2……pn
为这n个自然数的一个排列,考虑元素pi(i=1,2,……n),如果比pi大的而且排在
pi前面的元素有ti个,就说pi这个元素的逆序对是ti。全体元素的逆序对之和为
T1=t1+t2+……+tn
而每一个半序序列就有一个T1,求出所有半序序列的 Ti的和T.
再用T除以半序序列的个数 C2nn*n!(C2nn表示从2n个不同元素中,任取n个元素并成一组)
平均逆序对个数可表示为:T/C2nn*n!.
为这n个自然数的一个排列,考虑元素pi(i=1,2,……n),如果比pi大的而且排在
pi前面的元素有ti个,就说pi这个元素的逆序对是ti。全体元素的逆序对之和为
T1=t1+t2+……+tn
而每一个半序序列就有一个T1,求出所有半序序列的 Ti的和T.
再用T除以半序序列的个数 C2nn*n!(C2nn表示从2n个不同元素中,任取n个元素并成一组)
平均逆序对个数可表示为:T/C2nn*n!.
更多追问追答
追问
.........
这T怎么求啊
完全没有规律
不能算出具体数值吗?
追答
不同的半序序列对应不同的T1,而我们要求的是平均个数,所以没有规律。
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询