[:is] Math colloquium
Fyrirlesari: Anders Karl Claesson, Háskóli Íslands
Titill: On the problem of Hertzsprung and similar problems
Staðsetning: Via Zoom. Link to be sent.
Tími: Þriðjudag 19.janúar kl.10:00
Ágrip:
Drawing on a problem posed by Hertzsprung in 1887 (sometimes called the n-kings problem), we say that a permutation w contains the Hertzsprung pattern u if there is factor w(d+1)w(d+2)…w(d+k) of w such that w(d+1)-u(1) = … = w(d+k)-u(k). Using a combination of the Goulden-Jackson cluster method (which we explain) and the transfer-matrix method we determine the joint distribution of occurrences of any set of (incomparable) Hertzsprung patterns, thus substantially generalizing earlier results by Jackson et al. on the distribution of ascending and descending runs in permutations. We apply our results to the problem of counting permutations up to pattern-replacement equivalences, and using pattern-rewriting systems—a new formalism similar to the much studied string-rewriting systems—we solve a couple of open problems raised by Linton et al. in 2012.
[:en]
Math colloquium
Speaker: Anders Karl Claesson, University of Iceland
Title: On the problem of Hertzsprung and similar problems
Room: Via Zoom. Link to be sent.
Time: Tuesday January 19th, 10:00 hrs
Abstract:
Drawing on a problem posed by Hertzsprung in 1887 (sometimes called the n-kings problem), we say that a permutation w contains the Hertzsprung pattern u if there is factor w(d+1)w(d+2)…w(d+k) of w such that w(d+1)-u(1) = … = w(d+k)-u(k). Using a combination of the Goulden-Jackson cluster method (which we explain) and the transfer-matrix method we determine the joint distribution of occurrences of any set of (incomparable) Hertzsprung patterns, thus substantially generalizing earlier results by Jackson et al. on the distribution of ascending and descending runs in permutations. We apply our results to the problem of counting permutations up to pattern-replacement equivalences, and using pattern-rewriting systems—a new formalism similar to the much studied string-rewriting systems—we solve a couple of open problems raised by Linton et al. in 2012.
.[:]