Sökning: onr:"swepub:oai:DiVA.org:mdh-50954" >
Expected inversion ...
Expected inversion number after k adjacent transpositions
-
- Eriksson, Henrik (författare)
- KTH, Sweden
-
- Eriksson, Kimmo, 1967- (författare)
- KTH, Sweden
-
- Sjöstrand, Jonas (författare)
- KTH, Sweden
-
(creator_code:org_t)
- 2000
- 2000
- Engelska.
-
Ingår i: Formal Power Series and Algebraic Combinatorics. - 3540672478 ; , s. 677-685
- Relaterad länk:
-
https://urn.kb.se/re...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas