A384705 Number of binary shuffle squares of length 2n with prefix 0, that can be obtained from a unique binary word of length n.

1, 3, 11, 38, 135, 475, 1681, 5875, 20641, 71956, 250448, 869332, 3015496, 10440429

Offset: 1

Author

Bartlomiej Pawlik, Jun 07 2025

Keywords

• nonn
• hard

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.

Examples

			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).
		

Links

• D. Datko and Bartlomiej Pawlik, Roots of Binary Shuffle Squares, Symmetry 17/2: 305 (2025).

Crossrefs

Cf. A191755 (number of all binary shuffle squares with length 2n).

Programs

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

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