A327990 The Fibonacci Codes. Irregular triangle T(n, k) with n >= 0 and 0 <= k < A000045(n+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

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

Table of n, a(n) for n=0..53.

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

Cf. A309896, A000045, A001924.

Sequence in context: A187818 A365454 A059090 * A133115 A210192 A249755

Adjacent sequences: A327987 A327988 A327989 * A327991 A327992 A327993

Keyword

nonn,tabf

Author

Peter Luschny, Oct 08 2019

Status

approved