The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A268084 Minimum number of occurrences of abelian squares in a binary word of length n. 0
0, 0, 0, 1, 2, 3, 4, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 17, 18, 20, 21, 23, 24, 26, 28, 29, 30, 32, 34, 35, 37, 39, 41, 43, 44 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,5
COMMENTS
A binary word is a sequence each member of which belongs to an alphabet of size 2 such as {a,b}. An abelian square is an even length factor whose first half is an anagram of the second half, for example abaaaaab.
One can also ask for the minimum number of distinct abelian squares in a word of length n and the minimum number of nonequivalent abelian squares. Two abelian squares are equivalent if they are anagrams of each other.
For example the word ababbaaabaa contains 5 distinct abelian squares, aa, bb, abab, abba and baaaba, but only 4 nonequivalent abelian squares since abab and abba are equivalent. It's conjectured that both the minimum number of distinct abelian squares in a binary word of length n and the minimum number of nonequivalent abelian squares equal floor(n/4)
REFERENCES
G. Fici and A. Saarela, On the minimum number of abelian squares in a word, Combinatorics and Algorithmics of Strings, Dagstuhl Reports, 4(2014), pages 34-35.
LINKS
A. S. Fraenkel, J. Simpson, and M. Paterson, On weak circular squares in binary words, Combinatorial Pattern Matching, Springer Berlin Heidelberg, 1997, pages 76-82.
Jamie Simpson, Solved and unsolved problems about abelian squares, arXiv:1802.04481 [math.CO], 2018.
EXAMPLE
For example the least number of occurrences of abelian squares in a binary word of length 11 is 7. There are 12 words which attain this minimum. One is ababbaaabaa which contains 3 occurrences of aa and one each of bb, abab, abba and baaaba.
PROG
(Python)
from itertools import product, permutations
def count_overlaps(subs, s):
c = i = 0
while i != -1:
i = s.find(subs, i)
if i != -1: c += 1; i += 1
return c
def a(n): # only check words starting with 0 by symmetry
ar = ("".join(u) for r in range(1, n//2+1) for u in product("01",
repeat=r))
abel_squares = set(w+"".join(wp) for w in ar for wp in permutations(w))
words = ("0"+"".join(w) for w in product("10", repeat=n-1))
themin = n*n
for w in words:
numw = 0
for s in abel_squares:
numw += count_overlaps(s, w)
if numw >= themin: break
else: themin = min(themin, numw)
return themin
print([a(n) for n in range(1, 14)]) # Michael S. Branicky, Dec 20 2020
CROSSREFS
A262249 gives the maximum number of distinct abelian squares in a binary word of length n and A262265 gives the maximum number of nonequivalent abelian squares.
Sequence in context: A127035 A325106 A309687 * A261085 A017876 A356860
KEYWORD
nonn,more
AUTHOR
Jamie Simpson, Jan 26 2016
EXTENSIONS
a(21)-a(35) from Lars Blomberg, Feb 04 2016
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 23:43 EDT 2024. Contains 372666 sequences. (Running on oeis4.)