A262265
Maximum possible number of inequivalent abelian squares occurring in a binary word of length n.
Original entry on oeis.org
0, 1, 1, 2, 3, 4, 4, 6, 6, 7, 8, 10, 10, 11, 12, 15, 16, 17, 17, 19, 21, 22, 23, 25, 26, 28, 29, 31, 32, 34, 36, 37, 39, 41
Offset: 1
For n = 7 the word 0011001 contains 5 distinct abelian squares (00, 11, 0110, 1001, 001100) but only 4 of these are inequivalent, since 0110 and 1001 are equivalent.
- Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walén, Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word, Slides, DLT 2014.
- Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walén, Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word, in A. M. Shur and M. V. Volkov (Eds.): DLT 2014, LNCS 8633, Springer, pp. 215-226, 2014.
- Jamie Simpson, Solved and unsolved problems about abelian squares, arXiv:1802.04481 [math.CO], 2018.
-
from itertools import product, permutations
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))
maxn = -1
for w in words:
seen = set()
for s in abel_squares:
if s in w: seen.add(tuple(sorted(s)))
maxn = max(maxn, len(seen))
return maxn
print([a(n) for n in range(1, 14)]) # Michael S. Branicky, Dec 20 2020
A268084
Minimum number of occurrences of abelian squares in a binary word of length n.
Original entry on oeis.org
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
Offset: 1
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.
- 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.
- 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.
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.
-
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
Showing 1-2 of 2 results.
Comments