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