| 1. |
- Eriksen, Niklas, 1974-, et al.
(författare)
-
Diagonal checker-jumping and Eulerian numbers for color-signed permutations
- 2000
-
Ingår i: The Electronic Journal of Combinatorics. - Clemson, USA : Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 7
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce color-signed permutations to obtain a very explicit combinatorial interpretation of the q-Eulerian identities of Brenti and some generalizations. In particular, we prove an identity involving the golden ratio, which allows us to compute upper bounds on how high a checker can reach in a classical checker-jumping problem, when the rules are relaxed to allow also diagonal jumps.
|
|
| 2. |
- Eriksson, Henrik, et al.
(författare)
-
Exact expectations for random graphs and assignments
- 2003
-
Ingår i: Combinatorics, probability & computing. - 0963-5483 .- 1469-2163. ; 12, s. 401-412
-
Tidskriftsartikel (refereegranskat)abstract
- For a random graph on n vertices where the edges appear with individual rates, we give exact formulas for the expected time at which the number of components has gone down to k and the expected length of the corresponding minimal spanning forest.For a random bipartite graph we give a formula for the expected time at which a k-assignment appears. This result has a bearing on the random assignment problem.
|
|
| 3. |
- Eriksson, Henrik, et al.
(författare)
-
Expected inversion number after k adjacent transpositions
- 2000
-
Ingår i: Formal Power Series and Algebraic Combinatorics. - 3540672478 ; , s. 677-685
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 4. |
- Eriksson, Henrik, et al.
(författare)
-
Note on the lamp lighting problem
- 2001
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 27:03-feb, s. 357-366
-
Tidskriftsartikel (refereegranskat)abstract
- We answer some questions concerning the so-called sigma -game of Sutner [Linear cellular automata and the Garden of Eden, Math. Intelligencer 11 (1989), 49-53]. It is played on a graph where each vertex has a lamp, the light of which is toggled by pressing any vertex with an edge directed to the lamp. For example, we show that every configuration of lamps can be lit if and only if the number of complete matchings in the graph is odd. In the special case of an orthogonal grid one gets a criterion for whether the number of monomer-dimer tilings of an m x n grid is odd or even.
|
|
| 5. |
- Eriksson, Henrik, et al.
(författare)
-
Sorting a bridge hand
- 2001
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 241:1-3, s. 289-300
-
Tidskriftsartikel (refereegranskat)abstract
- Sorting a permutation by block moves is a task that every bridge player has to solve every time she picks up a new hand of cards. It is also a problem for the computational biologist, for block moves are a fundamental type of mutation that can explain why genes common to two species do not occur in the same order in the chromosome, It is not known whether there exists an optimal sorting procedure running in polynomial time. Bafna and Pevzner gave a polynomial time algorithm that sorts any permutation of length n in at most 3n/4 moves. Our new algorithm improves this to [(2n - 2)/3] for n greater than or equal to 9. For the reverse permutation, we give an exact expression for the number of moves needed, namely [(n + 1)/2]. Computations of Bafha and Pevzner up to n = 10 seemed to suggest that this is the worst case; but as it turns out, a first counterexample occurs for n = 13, i.e. the bridge player's case. Professional card players never sort by rank, only by suit. For this case, we give a complete answer to the optimal sorting problem.
|
|
| 6. |
- Eriksson, Henrik, et al.
(författare)
-
Sorting a bridge hand.
- 2001
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 241:1-3, s. 289-300
-
Tidskriftsartikel (refereegranskat)
|
|
| 7. |
- Andrews, George, et al.
(författare)
-
Integer Partitions
- 2004
-
Bok (populärvet., debatt m.m.)
|
|
| 8. |
- Dalevi, Daniel A., et al.
(författare)
-
Measuring genome divergence in bacteria : A case study using Chlamydian data
- 2002
-
Ingår i: Journal of Molecular Evolution. - New York, USA : Springer-Verlag New York. - 0022-2844 .- 1432-1432. ; 55, s. 24-36
-
Tidskriftsartikel (refereegranskat)abstract
- We have studied the relative contribution of inversions, transpositions, deletions, and nucleotide substitutions to the evolution of Chlamydia trachomatis and Chlamydia pneumoniae. The minimal number of rearrangement events required for converting the gene order structure of one genome into that of the other was estimated to 59 6 events, including 13% inversions, 38% short inversions, and 49% transpositions. In contrast to previous findings, no examples of horizontal gene transfer subsequent to species divergence were identified, nor any evidence for an excessive number of tandem gene duplications. A statistical model was used to compare nucleotide frequencies for a set of genes uniquely present in one species to a set of orthologous genes present in both species. The two data sets were not significantly different, which is indicative of a low frequency of horizontal gene transfer events. This is based on the assumption that a foreign gene of different nucleotide content will not have become completely ameliorated, as verified by simulations of the amelioration rate at twofold and fourfold degenerate codon sites. The frequencies of nucleotide substitutions at twofold and fourfold degenerate sites, deletions, inversions, and translocations were estimated to 1.42, 0.62, 0,18, 0.01, and 0.01 per site, respectively.
|
|
| 9. |
|
|
| 10. |
|
|
