A306893 Number of distinct binary strings in the n-th Fibonacci shuffle set.

1, 1, 2, 5, 28, 572, 87210, 379629720, 336691526641470, 1730145467127958158326862, 10298346936926006723717705424338819472320, 408365746142143027393604600897014805299276160859821396471640832240, 124021818977464152348319837503281224966237629433185201999567260096859939574786766596034209404972486842291250

Offset

1,3

Comments

The sequence of Fibonacci shuffle sets is defined as follows: X_1 = {0}, X_2 = {01}, and X_{n+2} is the shuffle of X_{n+1} and X_n. Here the shuffle of two sets of strings X and Y is the union, over all x in X and y in Y, of s(x,y), the shuffle set of x and y. And s(x,y) is the set of all strings z that arise from shuffling x and y. More precisely, s(x,y) consists of all strings z such that if each letter of z is marked with either a ' or a ", then the primed letters spell out x (in order) and the double-primed letters spell out y. For example, s(ab,c) = { abc, acb, cab }.

Elements of X_n represent incomplete Dyck words with A000045(n) opening parentheses denoted by 0s, and A000045(n-1) closing parentheses denoted by 1s. - Max Alekseyev, Feb 12 2024

Links

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

Formula

a(n) = binomial(F(n+1),F(n)) * (F(n-2)+1) / (F(n)+1), where F = A000045 are Fibonacci numbers. - Max Alekseyev, Feb 12 2024

Example

X_3 = {010, 001} and X_4 = {01010, 00110, 00101, 01001, 00011}, so a(3) = 2 and a(4) = 5.

Prog

(Python)
from itertools import combinations
def s(x, y):
    lxy, setxy = len(x) + len(y), set()
    setlxy, sxy = set(range(lxy)), [0 for i in range(lxy)]
    for xinds in combinations(range(lxy), len(x)):
        yinds = sorted(setlxy-set(xinds))
        for i, c in enumerate(x): sxy[xinds[i]] = c
        for i, c in enumerate(y): sxy[yinds[i]] = c
        setxy.add("".join(sxy))
    return setxy
def aupto(n):
    Xnm2, Xnm1, alst = {'0'}, {'01'}, [1, 1]
    while len(alst) < n:
        Xn = set()
        for i, x in enumerate(Xnm2, start=1):
            for y in Xnm1:
                Xn |= s(x, y)
        Xnm2, Xnm1 = Xnm1, Xn
        alst.append(len(Xn))
    return alst[:n]
print(aupto(6)) # Michael S. Branicky, Jun 07 2022
(PARI) { a306893(n) = binomial(fibonacci(n+1), fibonacci(n)) * (fibonacci(n-2)+1) \ (fibonacci(n)+1); } \\ Max Alekseyev, Feb 12 2024

Crossrefs

Cf. A000045.

Sequence in context: A316972 A068069 A292499 * A105787 A110497 A000472

Adjacent sequences: A306890 A306891 A306892 * A306894 A306895 A306896

Keyword

nonn

Author

Jeffrey Shallit, Mar 15 2019

Extensions

Terms a(8) onward from Max Alekseyev, Feb 12 2024

Status

approved