Subsequence frequency in binary words

DOI10.1016/J.DISC.2024.113928MaRDI QIDQ6204345OpenAlexFDO

Authors Krishna Menon, Anurag Singh

Publication date 27 March 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

pattern avoidanceWilf equivalencebinary wordssubsequence frequency

Mathematics Subject Classification ID

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

Abstract: The numbers we study in this paper are of the form $B_{n,p}(k)$, which is the number of binary words of length $n$ that contain the word $p$ (as a subsequence) exactly $k$ times. Our motivation comes from the analogous study of pattern containment in permutations. In our first set of results, we obtain explicit expressions for $B_{n,p}(k)$ for small values of $k$. We then focus on words $p$ with at most $3$ runs and study the maximum number of occurrences of $p$ a word of length $n$ can have. We also study the internal zeros in the sequence $(B_{n,p}(k){)}_{kgeq0}$ for fixed $n$ and discuss the unimodality and log-concavity of such sequences.

Recommendations

• Finding binary words with a given number of subsequences
• scientific article; zbMATH DE number 1868881
• scientific article; zbMATH DE number 759631
• Counting occurrences of a pattern of length three with at most two distinct letters in a \(k\)-ary word
• scientific article; zbMATH DE number 1431669

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 1919509 (Why is no real title available?)
• Algorithms for subsequence combinatorics
• Algorithms for the Longest Common Subsequence Problem
• Counting occurrences of 132 in a permutation
• Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three
• Length-four pattern avoidance in inversion sequences
• On the maximum number of distinct factors of a binary string
• Pattern avoidance of \([4,k]\)-pairs in circular permutations
• Pattern frequency sequences and internal zeros
• Permutations with one or two 132-subsequences
• Reconstruction from subsequences.
• Restricted Grassmannian permutations
• String overlaps, pattern matching, and nontransitive games
• Strings with maximally many distinct subsequences and substrings
• Subsequence numbers and logarithmic concavity
• The enumeration of permutations with a prescribed number of ``forbidden patterns
• The number of permutations containing exactly one increasing subsequence of length three
• The number of permutations with exactly \(r\) 132-subsequences is \(P\)-recursive in the size!

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Subsequence frequency in binary words

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