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

Author

Peter Luschny, Oct 08 2019

Keywords

• nonn
• tabf

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)).

Examples

			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]
		

Crossrefs

Cf. A309896, A000045, A001924.

Programs

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))