login
The Fibonacci Codes. Irregular triangle T(n, k) with n >= 0 and 0 <= k < A000045(n+1).
1

%I #9 Oct 09 2019 01:58:49

%S 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,

%T 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,

%U 1

%N The Fibonacci Codes. Irregular triangle T(n, k) with n >= 0 and 0 <= k < A000045(n+1).

%C The Fibonacci codes are binary strings enumerated in an irregular triangle FC(n, k). The first few are shown below in the Example section.

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

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

%C Fibonacci codes are represented here through

%C T(n, k) = Sum_{j=0..m} (c[j] + 1)*2^j,

%C where c = FC(n, k) and m = length(FC(n, k)).

%e The Fibonacci codes start:

%e [0] [[]]

%e [1] [[0]]

%e [2] [[00][0]]

%e [3] [[000][00][0]]

%e [4] [[010][0000][000][00][0]]

%e [5] [[0010][0100][00000][010][0000][000][00][0]]

%e [6] [[0110][00010][00100][01000][000000][0010][0100][00000][010][0000][000][00][0]]

%e [7] [[00110][01010][000010][01100][000100][001000][010000][0000000][0110][00010][00100][01000][000000][0010][0100][00000][010][0000][000][00][0]]

%e The encoding of the Fibonacci codes start:

%e [0] [0]

%e [1] [1]

%e [2] [3, 1]

%e [3] [7, 3, 1]

%e [4] [9, 15, 7, 3, 1]

%e [5] [19, 17, 31, 9, 15, 7, 3, 1]

%e [6] [21, 39, 35, 33, 63, 19, 17, 31, 9, 15, 7, 3, 1]

%e [7] [43, 41, 79, 37, 71, 67, 65, 127, 21, 39, 35, 33, 63, 19, 17, 31, 9, 15, 7, 3, 1]

%o (SageMath)

%o @cached_function

%o def FibonacciCodes(n):

%o if n == 0 : return [[]]

%o if n == 1 : return [[0]]

%o A = [c.conjugate() for c in Compositions(n) if not(1 in c)]

%o B = [[i-1 for i in a] for a in A]

%o return B + FibonacciCodes(n-1)

%o def A327990row(n):

%o FC = FibonacciCodes(n)

%o B = lambda C: sum((c+1)*2^i for (i, c) in enumerate(C))

%o return [B(c) for c in FC]

%o for n in (0..6): print(A327990row(n))

%Y Cf. A309896, A000045, A001924.

%K nonn,tabf

%O 0,3

%A _Peter Luschny_, Oct 08 2019