Volume 8
n° 1 (2006), pp. 189-214| author: | Sylvie Corteel, Guy Louchard and R. Pemantle |
|---|---|
| title: | Common intervals in permutations |
| keywords: | permutations, intervals |
| abstract: | An interval of a permutation is a consecutive substring consisting of consecutive symbols. For example, 4536 is an interval in the permutation 71453682. These arise in genetic applications. For the applications,
it makes sense to generalize so as to allow gaps of bounded size
δ-1 , both in the locations and the symbols. For example, 4527
has gaps bounded by 1 (since 3 and 6 are missing) and is therefore a
δ -interval of 389415627 for δ=2 .
After analyzing the distribution of the number of intervals of a uniform random permutation, we study the number of 2-intervals. This is exponentially large, but tightly clustered around its mean. Perhaps surprisingly, the quenched and annealed means are the same. Our analysis is via a multivariate generating function enumerating pairs of potential 2-intervals by size and intersection size. |
| If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. | |
| reference: | Sylvie Corteel and Guy Louchard and R. Pemantle (2006), Common intervals in permutations, Discrete Mathematics and Theoretical Computer Science 8, pp. 189-214 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dm080112.ps.gz (160 K) |
| ps-source: | dm080112.ps (393 K) |
| pdf-source: | dm080112.pdf (292 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.
Automatically produced on Fri Jul 14 14:50:25 CEST 2006 by falk