exercise:4627c2636c

Given any ordering [math]\sigma[/math] of [math]\{1, 2, \ldots, n\}[/math], we can define [math]\sigma^{-1}[/math], the inverse ordering of [math]\sigma[/math], to be the ordering in which the [math]i[/math]th element is the position occupied by [math]i[/math] in [math]\sigma[/math]. For example, if [math]\sigma = (1, 3, 5, 2, 4, 7, 6)[/math], then [math]\sigma^{-1} = (1, 4, 2, 5, 3, 7, 6)[/math]. (If one thinks of these orderings as permutations, then [math]\sigma^{-1}[/math] is the inverse of [math]\sigma[/math].)

A fall occurs between two positions in an ordering if the left position is occupied by a larger number than the right position. It will be convenient to say that every ordering has a fall after the last position. In the above example, [math]\sigma^{-1}[/math] has four falls. They occur after the second, fourth, sixth, and seventh positions. Prove that the number of rising sequences in an ordering [math]\sigma[/math] equals the number of falls in [math]\sigma^{-1}[/math].