Mathematics — Probability · card-shuffling-rising-sequences
Problem
Given any ordering σ of {1,2,…,n}, we can define σ−1, the inverse ordering of σ, to be the ordering in which the ith element is the position occupied by i in σ. For example, if σ=(1,3,5,2,4,7,6), then σ−1=(1,4,2,5,3,7,6). (If one thinks of these orderings as permutations, then σ−1 is the inverse of σ.)
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, σ−1 has four falls. They occur after the second, fourth, sixth, and seventh positions. Prove that the number of rising sequences in an ordering σ equals the number of falls in σ−1.