Consider as given n line segments between points with coordinates (0, i) and (1, ai), for i = 0, 1, . . . , n ? 1, where ai ? { 0, 1, . . . , n ? 1 } and ai 6= aj for i 6= j. Show that the number of crossings between the line segments equals the number of inversions in the sequence a0, a1, . . . , an?1.

Exercise 1 Consider as given n line segments between points with coordinates (0, i) and (1,a), for i-0,1, ,n-1, where aj E 0,1 Show that the number of crossings between the line segments equals the number of inversions in the sequence ao, a\,... , an-1- and ai aj Tor l^j