A347582 Number of length-2n binary strings of the form xxyy.

2, 6, 20, 54, 146, 346, 848, 1922, 4424, 9810, 21816, 47598, 103730, 223498, 480542, 1025956, 2184362, 4629670, 9786512, 20618936, 43340862, 90870526, 190141128, 397049128, 827675318

Offset

1,1

Links

Table of n, a(n) for n=1..25.

Formula

A347583(n) <= a(n) <= A347583(n) + 2^n. - Michael S. Branicky, Jan 23 2022

Example

a(2) = 6: {0000, 0011, 0101, 1010, 1100, 1111}.

Prog

(Python)
from itertools import product
from functools import cache
@cache
def b(n): # length-2n binary strings of the form ww
    return set(w+w for w in product(b"01", repeat=n))
def a(n):
    return len(set(s+t for i in range(n) for s in b(i) for t in b(n-i)))
print([a(n) for n in range(1, 18)]) # Michael S. Branicky, Jan 23 2022
(Python) # bit-based version
from itertools import product
def b(n): # length-2n binary strings of the form ww
    if n == 0: yield 0
    for i in range(2**n):
        yield (i << n) + i
def a(n):
    st = set()
    for i in range(n):
        for w in b(i):
            s = w << (2*(n-i))
            for t in b(n-i):
                st.add(s+t)
    return len(st)
print([a(n) for n in range(1, 20)]) # Michael S. Branicky, Jan 25 2022

Crossrefs

Cf. A347583, which requires x and y to be nonempty.

Sequence in context: A066397 A060344 A363600 * A045655 A303307 A321192

Adjacent sequences: A347579 A347580 A347581 * A347583 A347584 A347585

Keyword

nonn,more

Author

Jeffrey Shallit, Jan 23 2022

Extensions

a(18)-a(21) from Michael S. Branicky, Jan 23 2022

a(22)-a(25) from Michael S. Branicky, Jan 25 2022

Status

approved