Forbidden substrings on weighted alphabets

zbMATH Open1207.05008arXiv0906.3763MaRDI QIDQ3058991

Amy N. Myers

Publication date: 8 December 2010

Abstract: In an influential 1981 paper, Guibas and Odlyzko constructed a generating function for the number of length n strings over a finite alphabet that avoid all members of a given set of forbidden substrings. Here we extend this result to the case in which the strings are weighted. This investigation was inspired by the problem of counting compositions of an integer n that avoid all compositions of a smaller integer m, a notion which arose from the consideration of one-sided random walks.

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

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15) Permutations, words, matrices (05A05)

Related Items (4)

ON THE VISUALIZATION OF STRINGS AND FRACTALS OF SOME FORBIDDEN WORDS ⋮ Title not available (Why is that?) ⋮ Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences ⋮ Title not available (Why is that?)

This page was built for publication: Forbidden substrings on weighted alphabets

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