OFFSET
1,2
COMMENTS
A shuffle square is a word obtained by self-shuffle (i.e. by mixing two copies of the same word, keeping the order of letters from each copy). For example, the shuffle square "tuteurer" can be obtained by self-shuffling the word "tuer" (tu-t-e-u-r-er). The word 0011 is a shuffle square, while 0110 is not.
LINKS
D. Datko and Bartlomiej Pawlik, Roots of Binary Shuffle Squares, Symmetry 17/2: 305 (2025).
EXAMPLE
a(4) = 38 since there are exactly 41 binary shuffle squares of length 8 starting with 0, however three of them can be obtained from more than one binary word:
00100100 can be obtained from 0010 (e.g., 001-001-0-0) and from 0100 (e.g., 0-0-100-100);
00101011 from 0011 (001-0-1-011) and from 0101 (0-0-10-101-1);
00110011 from 0011 (e.g., 0011-0011) and form 0101 (e.g., 0-0-1-1-0-0-1-1).
PROG
(Python)
from collections import Counter
from itertools import combinations, combinations_with_replacement as cwr
from sympy.utilities.iterables import multiset_permutations as mp
def self_shuffles(w):
sswset, n = set(), len(w)
set2n, ssw = set(range(2*n)), [0 for i in range(2*n)]
for s in combinations(list(range(2*n)), n):
nots = sorted(set2n-set(s))
for i, c in enumerate(w): ssw[s[i]] = ssw[nots[i]] = c
sswset.add("".join(ssw))
return sswset
def a(n):
if n == 0: return 1
u = 0
for w in cwr("10", n-1): # "base" or "sorted" roots
c = Counter()
for pw in mp(w): # iterate over permutations of these
pw = "0" + "".join(pw) # enforce prefix 0
sspw = self_shuffles(pw) # build self_shuffles from these roots
c.update(sspw)
u += sum(1 for x in c if c[x] == 1) # count results w/unique roots
return u
print([a(n) for n in range(1, 10)]) # Michael S. Branicky, Jun 17 2025
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Bartlomiej Pawlik, Jun 07 2025
EXTENSIONS
a(10)-a(12) corrected by Michael S. Branicky, Jun 15 2025
a(13) from Michael S. Branicky, Jun 17 2025
a(14) from Sean A. Irvine, Jun 24 2025
a(15) from Michael S. Branicky, Sep 08 2025
STATUS
approved