A327992 - OEIS

%I #33 Mar 17 2020 15:19:08

%S 1,11,111,101,1111,1101,1011,11111,1001,11101,11011,10111,111111,

%T 11001,10101,10011,111101,111011,110111,101111,1111111,10001,111001,

%U 110101,101101,110011,101011,100111,1111101,1111011,1110111,1101111,1011111,11111111

%N The binary Fibonacci compositions. Irregular triangle with n >= 0 where the length of row n is Fibonacci(n) for n > 0.

%C Taking up an idea of Cayley the binary Fibonacci compositions are defined as the conjugates of the compositions of n + 1 which do not have a part '1'. a(0) = 1 by convention and for n > 0 the representation of the composition c is given by Sum_{c} (2 - c[j])*2^j, where the c[j] are the parts of the composition c. With this interpretation the sequence is a permutation of the positive odd numbers (A005408).

%D A. Cayley, Theorems in Trigonometry and on Partitions, Messenger of Mathematics, 5 (1876), pp. 164, 188. Also in Mathematical Papers Vol. 10, n. 634, p. 16.

%H Peter Luschny, <a href="/A327992/b327992.txt">Table of n, a(n) for row 0..19</a>

%F The number of zeros in all binary Fibonacci compositions of n equal the number of elements in all subsets of {1, 2, ..., n} with no consecutive integers. (For example, the number of zeros in row 7 (see the triangle below) is 20 = A001629(6).)

%e The triangle starts:

%e [0] [    1]

%e [1] [   11]

%e [2] [  111]

%e [3] [  101,   1111]

%e [4] [ 1101,   1011,  11111]

%e [5] [ 1001,  11101,  11011,  10111, 111111]

%e [6] [11001,  10101,  10011, 111101, 111011, 110111, 101111, 1111111]

%e [7] [10001, 111001, 110101, 101101, 110011, 101011, 100111, 1111101, 1111011, 1110111, 1101111, 1011111, 11111111]

%e .

%e For instance, to compute T(7, 2) start with the composition [2, 3, 3]. Then take the conjugate, normalize the parts with 2 - c[j] and then represent the digits as an integer. The steps are:

%e [2, 3, 3] -> [1, 1, 2, 1, 2, 1] -> [1, 1, 0, 1, 0, 1] -> 110101 = T(7, 2).

%o (SageMath)

%o import functools

%o def alpha(P, Q): # order of compositions

%o     if len(P) < len(Q): return int(-1)

%o     if len(P) == len(Q):

%o         for i in range(len(P)):

%o             if P[i] < Q[i]: return int(-1)

%o             if P[i] > Q[i]: return int(1)

%o             return int(0)

%o     return int(0)

%o def compositions(n):

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

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

%o     sorted(B, key = functools.cmp_to_key(alpha))

%o     return B

%o def Int(c): # convert to decimal integer representation

%o     s = ""

%o     for t in c: s += str(t)

%o     return Integer(s) if s else 1

%o def A327992row(n):

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

%o     return [Int(c) for c in compositions(n)]

%o for n in (0..8): print(A327992row(n))

%Y Cf. A000045, A001629, A327993 (row sums).

%K nonn,tabf

%O 0,2

%A _Peter Luschny_, Oct 12 2019