ALGEBRAIC COMBINATORICS

no. 6
From Hertzsprung’s problem to pattern-rewriting systems
Claesson, Anders1
1 Science Institute University of Iceland Iceland
Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1257-1277.

Drawing on a problem posed by Hertzsprung in 1887, we say that a given permutation π∈𝒮 n contains the Hertzsprung pattern σ∈𝒮 k if there is a factor π(d+1)π(d+2)⋯π(d+k) of π such that π(d+1)-σ(1)=⋯=π(d+k)-σ(k). Using a combination of the Goulden–Jackson cluster method 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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.202
Classification: 05A05, 05A15, 68R05, 68R15, 68Q42
Keywords: Hertzsprung’s problem, cluster method, pattern, permutation, rewriting system.
Claesson, Anders 1

1 Science Institute University of Iceland Iceland
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2022__5_6_1257_0,
     author = {Claesson, Anders},
     title = {From {Hertzsprung{\textquoteright}s} problem to pattern-rewriting systems},
     journal = {Algebraic Combinatorics},
     pages = {1257--1277},
     publisher = {The Combinatorics Consortium},
     volume = {5},
     number = {6},
     year = {2022},
     doi = {10.5802/alco.202},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.202/}
}
TY  - JOUR
AU  - Claesson, Anders
TI  - From Hertzsprung’s problem to pattern-rewriting systems
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 1257
EP  - 1277
VL  - 5
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.202/
DO  - 10.5802/alco.202
LA  - en
ID  - ALCO_2022__5_6_1257_0
ER  - 
%0 Journal Article
%A Claesson, Anders
%T From Hertzsprung’s problem to pattern-rewriting systems
%J Algebraic Combinatorics
%D 2022
%P 1257-1277
%V 5
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.202/
%R 10.5802/alco.202
%G en
%F ALCO_2022__5_6_1257_0
Claesson, Anders. From Hertzsprung’s problem to pattern-rewriting systems. Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1257-1277. doi : 10.5802/alco.202. https://alco.centre-mersenne.org/articles/10.5802/alco.202/

[1] Abramson, Morton; Moser, William O. J. Permutations without rising or falling w-sequences, Ann. Math. Statist., Volume 38 (1967), pp. 1245-1254 | DOI | MR | Zbl

[2] Albert, Michael H.; Atkinson, Mike D. Simple permutations and pattern restricted permutations, Discrete Math., Volume 300 (2005) no. 1-3, pp. 1-15 | DOI | MR | Zbl

[3] Baader, Franz; Nipkow, Tobias Term rewriting and all that, Cambridge University Press, Cambridge, 1998, xii+301 pages | DOI | MR | Zbl

[4] Bergeron, François; Labelle, Gilbert; Leroux, Pierre Combinatorial species and tree-like structures, Encyclopedia of Mathematics and its Applications, 67, Cambridge University Press, Cambridge, 1998, xx+457 pages (Translated from the 1994 French original by Margaret Readdy, With a foreword by Gian-Carlo Rota) | MR | Zbl

[5] Bóna, Miklós Where the monotone pattern (mostly) rules, Discrete Math., Volume 308 (2008) no. 23, pp. 5782-5788 | DOI | MR | Zbl

[6] Book, Ronald V.; Otto, Friedrich String-rewriting systems, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1993, viii+189 pages | DOI | MR | Zbl

[7] Brändén, Petter; Claesson, Anders Mesh patterns and the expansion of permutation statistics as sums of permutation patterns, Electron. J. Combin., Volume 18 (2011) no. 2, Paper no. 5, 14 pages | MR | Zbl

[8] Brualdi, Richard A.; Deutsch, Emeric Adjacent q-cycles in permutations, Ann. Comb., Volume 16 (2012) no. 2, pp. 203-213 | DOI | MR | Zbl

[9] Caron, Anne-Cécile Linear bounded automata and rewrite systems: influence of initial configurations on decision properties, TAPSOFT ’91, Vol. 1 (Brighton, 1991) (Lecture Notes in Comput. Sci.), Volume 493, Springer, Berlin, 1991, pp. 74-89 | DOI | MR | Zbl

[10] Dotsenko, Vladimir; Khoroshkin, Anton Shuffle algebras, homology, and consecutive pattern avoidance, Algebra Number Theory, Volume 7 (2013) no. 3, pp. 673-700 | DOI | MR | Zbl

[11] Elizalde, Sergi; Noy, Marc Clusters, generating functions and asymptotics for consecutive patterns in permutations, Adv. in Appl. Math., Volume 49 (2012) no. 3-5, pp. 351-374 | DOI | MR | Zbl

[12] Flajolet, Philippe; Sedgewick, Robert Analytic combinatorics, Cambridge University Press, Cambridge, 2009, xiv+810 pages | DOI | MR | Zbl

[13] Gardner, Martin On the paradoxical situations that arise from nontransitive relations, Scientific American, Volume 231 (1974) no. 4, pp. 120-125

[14] Goulden, Ian P.; Jackson, David M. An inversion theorem for cluster decompositions of sequences with distinguished subsequences, J. London Math. Soc. (2), Volume 20 (1979) no. 3, pp. 567-576 | DOI | MR | Zbl

[15] Guibas, Leonidas J.; Odlyzko, Andrew M. String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A, Volume 30 (1981) no. 2, pp. 183-208 | DOI | MR | Zbl

[16] Hertzsprung, Severin En kombinationsopgave, Tidsskrift for mathematik, Volume 5 (1887), pp. 13-17 | Zbl

[17] Inc, OEIS Foundation The Online Encyclopedia of Integer Sequences, 2020 (http://oeis.org)

[18] Jackson, David M.; Read, Ronald C. A note on permutations without runs of given length, Aequationes Math., Volume 17 (1978) no. 2-3, pp. 336-343 | DOI | MR | Zbl

[19] Jackson, David M.; Reilly, James W. Permutations with a prescribed number of p-runs, Ars Combin., Volume 1 (1976) no. 1, pp. 297-305 | MR | Zbl

[20] Jackson, Davis M.; Aleliunas, Romas Decomposition based generating functions for sequences, Canadian J. Math., Volume 29 (1977) no. 5, pp. 971-1009 | DOI | MR | Zbl

[21] Kaplansky, Irving Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., Volume 50 (1944), pp. 906-914 | DOI | MR | Zbl

[22] Knuth, Donald E. Permutations, matrices, and generalized Young tableaux, Pacific J. Math., Volume 34 (1970), pp. 709-727 | DOI | MR | Zbl

[23] Kuszmaul, William Counting permutations modulo pattern-replacement equivalences for three-letter patterns, Electron. J. Combin., Volume 20 (2013) no. 4, Paper no. 10, 58 pages | MR | Zbl

[24] Kuszmaul, William; Zhou, Ziling New results on families of pattern-replacement equivalences, Discrete Math., Volume 343 (2020) no. 7, Paper no. 111878, 27 pages | DOI | MR | Zbl

[25] Linton, Steven; Propp, James; Roby, Tom; West, Julian Equivalence classes of permutations under various relations generated by constrained transpositions, J. Integer Seq., Volume 15 (2012) no. 9, Paper no. 12.9.1, 23 pages | MR | Zbl

[26] Myers, Amy N. Counting permutations by their rigid patterns, J. Combin. Theory Ser. A, Volume 99 (2002) no. 2, pp. 345-357 | DOI | MR | Zbl

[27] Newman, Max H. A. On theories with a combinatorial definition of “equivalence.”, Ann. of Math. (2), Volume 43 (1942), pp. 223-243 | DOI | MR | Zbl

[28] Novelli, Jean-Christophe; Schilling, Anne The forgotten monoid, Combinatorial representation theory and related topics (RIMS Kôkyûroku Bessatsu, B8), Res. Inst. Math. Sci. (RIMS), Kyoto, 2008, pp. 71-83 | MR | Zbl

[29] Penney, Walter 95. Penney-Ante, Journal of Recreational Mathematics, Volume 2 (1969), p. 241

[30] Pierrot, Adeline; Rossin, Dominique; West, Julian Adjacent transformations in permutations, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) (Discrete Math. Theor. Comput. Sci. Proc., AO), Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011, pp. 765-776 | MR | Zbl

[31] Riordan, John Permutations without 3-sequences, Bull. Amer. Math. Soc., Volume 51 (1945), pp. 745-748 | DOI | MR | Zbl

[32] Stanley, Richard P. Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 2012, xiv+626 pages | MR | Zbl

[33] Stanley, Richard P. An equivalence relation on the symmetric group and multiplicity-free flag h-vectors, J. Comb., Volume 3 (2012) no. 3, pp. 277-298 | DOI | MR | Zbl

Cited by Sources: