|
|
A327990
|
|
The Fibonacci Codes. Irregular triangle T(n, k) with n >= 0 and 0 <= k < A000045(n+1).
|
|
1
|
|
|
0, 1, 3, 1, 7, 3, 1, 9, 15, 7, 3, 1, 19, 17, 31, 9, 15, 7, 3, 1, 21, 39, 35, 33, 63, 19, 17, 31, 9, 15, 7, 3, 1, 43, 41, 79, 37, 71, 67, 65, 127, 21, 39, 35, 33, 63, 19, 17, 31, 9, 15, 7, 3, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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)).
|
|
LINKS
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|