第一題結果是n(n-1)/2
首先,前n個數(shù)都是從小到大排列的,沒有逆序數(shù)對.
然后,看2,前面n個數(shù)除了1以外的n-1個數(shù)都比它大,每一個都與它組成一對逆序數(shù)對,就有n-1個；
接著,看4,前面n個數(shù)除了1和3以外的n-2個數(shù)都比它大,每一個都與它組成一對逆序數(shù)對,就有n-2個；
.
到了2n-2時,就只有2n-1比它大,有一個逆序數(shù)對.
2n 是0.
加起來就是 0+1+2+……（n-1）=n(n-1)/2
第二題結果是n(n-1)
首先,前n個數(shù)都是從小到大排列的,沒有逆序數(shù)對.
然后,看2,前面2n-1個數(shù)除了1以外的2n-2個數(shù)都比它大,每一個都與它組成一對逆序數(shù)對,就有2n-2個；
接著,看4,前面2n-2個數(shù)除了1和3以外的2n-4個數(shù)都比它大,每一個都與它組成一對逆序數(shù)對,就有2n-4個；
.
到了2n-2時,有2個比它大,有2個逆序數(shù)對.
2n 是0.
加起來就是 2*【0+1+2+……（n-1）】=n(n-1)