OFFSET
0,3
COMMENTS
The Fibonacci codes are binary strings enumerated in an irregular triangle FC(n, k). The first few are shown below in the Example section.
The Fibonacci codes are for n > 1 defined recursively FC(n) = C(n) concatenated with FC(n-1), where C(n) are the conjugates of the compositions of n which do not have '1' as a part and the parts of which were reduced by 1. The recurrence is based in FC(0) = '' (empty string) and FC(1) = '0'.
The Fibonacci numbers are defined F(n) = A309896(2,n) = A000045(n+1) for n >= 0. Row FC(n) contains F(n) codes. A nonzero code is a code that does not consist entirely of zeros. The number of nonzero codes in row n is A001924(n-3) for n>=3.
Fibonacci codes are represented here through
T(n, k) = Sum_{j=0..m} (c[j] + 1)*2^j,
where c = FC(n, k) and m = length(FC(n, k)).
EXAMPLE
The Fibonacci codes start:
[0] [[]]
[1] [[0]]
[2] [[00][0]]
[3] [[000][00][0]]
[4] [[010][0000][000][00][0]]
[5] [[0010][0100][00000][010][0000][000][00][0]]
[6] [[0110][00010][00100][01000][000000][0010][0100][00000][010][0000][000][00][0]]
[7] [[00110][01010][000010][01100][000100][001000][010000][0000000][0110][00010][00100][01000][000000][0010][0100][00000][010][0000][000][00][0]]
The encoding of the Fibonacci codes start:
[0] [0]
[1] [1]
[2] [3, 1]
[3] [7, 3, 1]
[4] [9, 15, 7, 3, 1]
[5] [19, 17, 31, 9, 15, 7, 3, 1]
[6] [21, 39, 35, 33, 63, 19, 17, 31, 9, 15, 7, 3, 1]
[7] [43, 41, 79, 37, 71, 67, 65, 127, 21, 39, 35, 33, 63, 19, 17, 31, 9, 15, 7, 3, 1]
PROG
(SageMath)
@cached_function
def FibonacciCodes(n):
if n == 0 : return [[]]
if n == 1 : return [[0]]
A = [c.conjugate() for c in Compositions(n) if not(1 in c)]
B = [[i-1 for i in a] for a in A]
return B + FibonacciCodes(n-1)
def A327990row(n):
FC = FibonacciCodes(n)
B = lambda C: sum((c+1)*2^i for (i, c) in enumerate(C))
return [B(c) for c in FC]
for n in (0..6): print(A327990row(n))
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Peter Luschny, Oct 08 2019
STATUS
approved