Enumerating pairs of permutations with the same up-down form
✍ Scribed by C.L Mallows; L.A Shepp
- Publisher
- Elsevier Science
- Year
- 1985
- Tongue
- English
- Weight
- 482 KB
- Volume
- 54
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
For each sequence q = {qi} = ±1, i = 1 ..... n -1 let Nq = the number of permutations tr of 1, 2 ..... n with up-down sequence sgn(tri+x-tri) = th, i = 1 ..... n -1. Clearly Y.q (Nqln!) = 1 but what is the probability p, = Y.q (NJn!) 2 that two random permutations have the same up-down sequence? We show that p,, = (K"-tl, 1) where 1 = l(x, y)--1 and K "-1 is the iterated integral operator with K~b(x, y) = S~ S~ K(x, y; x', y')d~(x', y') dx' dy' on L2[0, 1] x [0, 1] where K(x, y; x', y') is 1 if (x-x')(y-y')>0 and 0 otherwise, and (f, g) = J~Io~/g. The eigenexpansion of K yields p,,~ca" as n--,,oo, where c~-1.6, a ~-0.55.
We also give a recatrsion formula for a polynomial whose coefficients are the frequencies of all the possible forms.