# Fibonacci sequences, binary numbers and compositions

Jump to navigation
Jump to search

## Fibonacci numbers[edit | edit source]

The Fibonacci numbers can be found in different ways in the sequence of binary strings.

Due to a bijection between binary strings and compositions,

every definition in terms of strings can also be given in terms of compositions, and vice versa.

- The number of binary words of length
*n*(length from first digit to last value 1 digit) without consecutive 0s is the Fibonacci number*F*_{n+1}. E.g., out of the 8 binary words of length 4, there are*F*_{5}= 5 without consecutive 0s - they are 0101, 1101, 1011, 0111 and 1111. - The number of strings of length
*n*without consecutive 1s is the Fibonacci number*F*_{n+2}. E.g., out of the 16 binary strings of length 4, there are*F*_{6}= 8 without consecutive 1s - they are 0000, 1000, 0100, 0010, 1010, 0001, 1001 and 0101.

(By symmetry, the number of strings of length*n*without consecutive 0s is also*F*_{n+2}.)

This corresponds to the following statement about compositions, quoted from OEIS A000045:

F(n)=number of compositions of n-1 with no part greater than 2.

Example: F(4)=3 because we have 3 = 1+1+1=1+2=2+1.

00 corresponds to 1+1+1, 01 corresponds to 1+2, 10 corresponds to 2+1.

- The number of binary words of length
*n*(length from first digit to last value 1 digit) without even numbers of consecutive 0s or 1s is the Fibonacci number*F*_{n}. E.g. out of 32 binary words of length 6 there are*F*_{6}= 8 with all runlengths odd - they are 000001, 010001, 000101, 010101, 011101, 000111, 010111 and 011111.

- The number of strings of length
*n*without an odd number of consecutive 1s is the Fibonacci number*F*_{n+1}.

This corresponds to the following statement about compositions, quoted from OEIS:

F(n) = number of compositions of n into odd parts;

e.g. F(6) counts 1+1+1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 1+5, 3+1+1+1, 3+3, 5+1.

- Further, the number of compositions of
*n*without addends equal to 1 is the Fibonacci number*F*_{n$-$1}.

E.g. out of the 8 compositions of 4 there are*F*_{3}= 2 without 1s - they are 2+2 and the 4 itself.

Out of the 16 compositions of 5 there are*F*_{4}= 3 without 1s - they are 2+3, 3+2 and the 5 itself.

## Fibonacci numbers of higher order[edit | edit source]

About the files showing two matrices:

- In the
**top matrices**blocks of n or more consecutive 0s are indicated by green dots. The number of columns without green dots between two green trigons is an element of the Fibonacci sequence of order n. - The number of compositions of natural numbers with no addend greater than n is a Fibonacci sequence of order n. Due to the bijection between compositions and binary numbers, this is what the
**bottom matrices**show: The blocks of n or more consecutive 1s are indicated by strong red squares. The number of columns without strong red squares, from the left side to a green trigon, is an element of the Fibonacci sequence of order n.

### Tribonacci numbers[edit | edit source]

### Tetranacci numbers[edit | edit source]

### Pentanacci numbers[edit | edit source]