Counting the palstars

MaRDI QIDQ405318zbMATH OpenFDO

Authors L. Bruce Richmond, Jeffrey Shallit

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.2318, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p25

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

analytic combinatoricsbordered wordpalindromepalstarprime palstar

Mathematics Subject Classification ID

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

Abstract: A palstar (after Knuth, Morris, and Pratt) is a concatenation of even-length palindromes. We show that, asymptotically, there are $Theta(alph{a}_k^n)$ palstars of length $2n$ over a $k$-letter alphabet, where $alph{a}_k$ is a constant such that $2k-1<alph{a}_k<2k-1over2$. In particular, $alph{a}_{2}doteq3.33513193$.

Review text

Summary: A palstar is a concatenation of even-length palindromes. We show that, asymptotically, there are \(\Theta(\alpha_k^n)\) palstars of length \(2n\) over a \(k\)-letter alphabet, where \(\alpha_k\) is a constant such that \(2k-1 \alpha_k 2k-{1 \over 2}\). In particular, \(\alpha_2\doteq 3.33513193\).

Recommendations

• Counting Star-Battle configurations
• scientific article; zbMATH DE number 5572871
• P-STARS
• scientific article; zbMATH DE number 2359497
• Representation numbers of stars
• scientific article; zbMATH DE number 965557

Cites work

• A Linear-Time On-Line Recognition Algorithm for ``Palstar
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• A note on bifix-free sequences (Corresp.)
• Analytic combinatorics
• Counting the palstars
• Fast Pattern Matching in Strings
• Inverse star, borders, and palstars

Cited in

(7)

• Borders, palindrome prefixes, and square prefixes
• Enumeration of two dimensional palindromes
• Palindromes dans les progressions arithmétiques
• scientific article; zbMATH DE number 5532152 (Why is no real title available?)
• Counting the palstars
• Palindromes in starlike trees
• Counting Star-Battle configurations

This page was built for publication: Counting the palstars

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