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

1, 11, 111, 101, 1111, 1101, 1011, 11111, 1001, 11101, 11011, 10111, 111111, 11001, 10101, 10011, 111101, 111011, 110111, 101111, 1111111, 10001, 111001, 110101, 101101, 110011, 101011, 100111, 1111101, 1111011, 1110111, 1101111, 1011111, 11111111

Offset: 0

Author

Peter Luschny, Oct 12 2019

Keywords

• nonn
• tabf

Comments

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

Examples

			The triangle starts:
[0] [    1]
[1] [   11]
[2] [  111]
[3] [  101,   1111]
[4] [ 1101,   1011,  11111]
[5] [ 1001,  11101,  11011,  10111, 111111]
[6] [11001,  10101,  10011, 111101, 111011, 110111, 101111, 1111111]
[7] [10001, 111001, 110101, 101101, 110011, 101011, 100111, 1111101, 1111011, 1110111, 1101111, 1011111, 11111111]
.
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:
[2, 3, 3] -> [1, 1, 2, 1, 2, 1] -> [1, 1, 0, 1, 0, 1] -> 110101 = T(7, 2).
		

References

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

Links

• Peter Luschny, Table of n, a(n) for row 0..19

Crossrefs

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

Programs

SageMath

import functools
def alpha(P, Q): # order of compositions
    if len(P) < len(Q): return int(-1)
    if len(P) == len(Q):
        for i in range(len(P)):
            if P[i] < Q[i]: return int(-1)
            if P[i] > Q[i]: return int(1)
            return int(0)
    return int(0)
def compositions(n):
    A = [c.conjugate() for c in Compositions(n+1) if not(1 in c)]
    B = [[2-i for i in a] for a in A]
    sorted(B, key = functools.cmp_to_key(alpha))
    return B
def Int(c): # convert to decimal integer representation
    s = ""
    for t in c: s += str(t)
    return Integer(s) if s else 1
def A327992row(n):
    if n == 0: return [1]
    return [Int(c) for c in compositions(n)]
for n in (0..8): print(A327992row(n))

Formula

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