Discrete Mathematics & Theoretical Computer Science, Vol 12, No 2 (2010)

Font Size:  Small  Medium  Large

The expected number of inversions after n adjacent transpositions

Mireille Bousquet-Melou


We give a new expression for the expected number of inversions in the product of n adjacent transpositions in the symmetric group S_{m+1}. We then derive from this expression the asymptotic behaviour of this number when n = n_m scales with m various ways. Our starting point is an equivalence, due to Eriksson et al., with a problem of weighted walks confined to a triangle area in the plane.

Full Text: PDF PostScript