From Hertzsprung's problem to pattern-rewriting systems

DOI10.5802/ALCO.202zbMATH Open1504.05008arXiv2012.15309OpenAlexW3115019648MaRDI QIDQ2109220FDOQ2109220

Authors: Anders Claesson 

Publication date: 20 December 2022

Published in: Algebraic Combinatorics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (1)

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

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)