Expected inversion number after k adjacent transpositions

(creator_code:org_t)

2000
2000
English.
In: Formal Power Series and Algebraic Combinatorics. - 3540672478 ; , s. 677-685

Abstract Subject headings

We give expressions for the expected number of inversions after t random adjacent transpositions have been performed on the identity permutation in Sn+1 The problem is a simplification of a problem motivated by genome evolution. For a fixed t and for all n greater than or equal to t, the expected number of inversions after t random adjacent transpositions isE-nt = t - 2/n ((t)(2)) + Sigma(r=2)(t) (-1)(r)/n(r) [2(r)C(r)((t)(r+1)) + 4d(r) ((t)(r))]where d(2) = 0, d(3) = 1, d(4) = 9, d(5) = 69,... is a certain integer sequence. An important part of the our method is the use of a heat. conduction analogy of the random walks, which guarantees certain properties of the solution.

By the author/editor: Eriksson, Henrik; Eriksson, Kimmo, ...; Sjöstrand, Jonas

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Mathematics; and Discrete Mathema ...

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.