From Hertzsprung's problem to pattern-rewriting systems

DOI10.5802/ALCO.202MaRDI QIDQ2109220zbMATH OpenOpenAlexFDO

Authors Anders Claesson

Publication date 20 December 2022

Published in Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2012.15309

zbMATH Keywords

permutationpatternrewriting systemcluster methodHertzsprung's problem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Exact enumeration problems, generating functions (05A15) Grammars and rewriting systems (68Q42) Combinatorics on words (68R15)

Abstract: Drawing on a problem posed by Hertzsprung in 1887, we say that a given permutation $piinmathcal{S}_n$ contains the Hertzsprung pattern $sigmainmathcal{S}_k$ if there is factor $pi(d+1)pi(d+2)cdotspi(d+k)$ of $pi$ such that $pi(d+1)-sigma(1)=cdots=pi(d+k)-sigma(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.

Recommendations

• scientific article; zbMATH DE number 1629834
• scientific article; zbMATH DE number 1303340
• Finite complete rewriting systems and the complexity of word problem
• scientific article; zbMATH DE number 522839
• Rewriting P systems: improved hierarchies
• scientific article; zbMATH DE number 2201367
• scientific article; zbMATH DE number 4006231
• scientific article; zbMATH DE number 3890721
• scientific article; zbMATH DE number 177826
• scientific article; zbMATH DE number 2068882

Cites work

• scientific article; zbMATH DE number 1638661 (Why is no real title available?)
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3529866 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• A note on permutations without runs of given length
• Adjacent \(q\)-cycles in permutations
• Adjacent transformations in permutations
• An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences
• An equivalence relation on the symmetric group and multiplicity-free flag \(h\)-vectors
• Analytic combinatorics
• Clusters, generating functions and asymptotics for consecutive patterns in permutations
• Counting permutations by their rigid patterns
• Counting permutations modulo pattern-replacement equivalences for three-letter patterns
• Decomposition Based Generating Functions for Sequences
• Equivalence classes of permutations under various relations generated by constrained transpositions
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• New results on families of pattern-replacement equivalences
• On theories with a combinatorial definition of 'equivalence'
• Permutations without 3-sequences
• Permutations without Rising or Falling $\omega$-Sequences
• Permutations, matrices, and generalized Young tableaux
• Shuffle algebras, homology, and consecutive pattern avoidance
• Simple permutations and pattern restricted permutations
• String overlaps, pattern matching, and nontransitive games
• Symbolic solution of certain problems in permutations
• Term Rewriting and All That
• The forgotten monoid
• Where the monotone pattern (mostly) rules

Cited in

(1)

• Turning cycle restrictions into mesh patterns via Foata's fundamental transformation

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: From Hertzsprung's problem to pattern-rewriting systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2109220)