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,2

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

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

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

Example

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

Prog

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

Crossrefs

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

Sequence in context: A004287 A061493 A093788 * A204847 A098759 A273977

Adjacent sequences: A327989 A327990 A327991 * A327993 A327994 A327995

Keyword

nonn,tabf

Author

Peter Luschny, Oct 12 2019

Status

approved