Subsequence frequency in binary words

DOI10.1016/J.DISC.2024.113928arXiv2306.07870OpenAlexW4391922018MaRDI QIDQ6204345FDOQ6204345

Authors: Krishna Menon, Anurag Singh 

Publication date: 27 March 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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)

Cites Work

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

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)