Department of Mathematics
University of Pennsylvania
Intervals of permutations and the singular variety method in
multivariate generatingfunctionology
(Joint with S. Corteel and G. Louchard)
Given a multivariate
generating function, how do we compute asymptotics of the
coefficients? If it is a rational function, the answer lies in
the pole variety. This talk will explain how this all works in
the context of the following combinatorial problem.
An interval of a permutation is a consecutive substring consisting of consectuve 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 delta - 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 2-interval of ****4*5*27****. The number of 2-intervals of a typical permutation is exponentially large, but tightly clustered around its mean. We are able to compute all this because we have a closed form generating function enumerating pairs of 2-intervals.
An interval of a permutation is a consecutive substring consisting of consectuve 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 delta - 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 2-interval of ****4*5*27****. The number of 2-intervals of a typical permutation is exponentially large, but tightly clustered around its mean. We are able to compute all this because we have a closed form generating function enumerating pairs of 2-intervals.