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

%I #21 Feb 12 2024 10:41:24

%S 1,1,2,5,28,572,87210,379629720,336691526641470,

%T 1730145467127958158326862,10298346936926006723717705424338819472320,

%U 408365746142143027393604600897014805299276160859821396471640832240,124021818977464152348319837503281224966237629433185201999567260096859939574786766596034209404972486842291250

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

%C 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 }.

%C 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

%F 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

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

%o (Python)

%o from itertools import combinations

%o def s(x, y):

%o lxy, setxy = len(x) + len(y), set()

%o setlxy, sxy = set(range(lxy)), [0 for i in range(lxy)]

%o for xinds in combinations(range(lxy), len(x)):

%o yinds = sorted(setlxy-set(xinds))

%o for i, c in enumerate(x): sxy[xinds[i]] = c

%o for i, c in enumerate(y): sxy[yinds[i]] = c

%o setxy.add("".join(sxy))

%o return setxy

%o def aupto(n):

%o Xnm2, Xnm1, alst = {'0'}, {'01'}, [1, 1]

%o while len(alst) < n:

%o Xn = set()

%o for i, x in enumerate(Xnm2, start=1):

%o for y in Xnm1:

%o Xn |= s(x, y)

%o Xnm2, Xnm1 = Xnm1, Xn

%o alst.append(len(Xn))

%o return alst[:n]

%o print(aupto(6)) # _Michael S. Branicky_, Jun 07 2022

%o (PARI) { a306893(n) = binomial(fibonacci(n+1),fibonacci(n)) * (fibonacci(n-2)+1) \ (fibonacci(n)+1); } \\ _Max Alekseyev_, Feb 12 2024

%Y Cf. A000045.

%K nonn

%O 1,3

%A _Jeffrey Shallit_, Mar 15 2019

%E Terms a(8) onward from _Max Alekseyev_, Feb 12 2024