FibonacciWords

The binary strings of length $n$ with no two consecutive 1s: count is the Fibonacci number $F(n+2)$.

✓ checked against that system · ! checked, with disagreements (hover a chip)OEISA132636✓↗A185357✓↗A000045✓↗A324969✓↗A274163✓↗

FibonacciWords(n)the length-$n$ binary strings with no two consecutive 1s

Typed signatures

Type	Package	Applies
(integer<0..>) -> indexed_collection<list<integer>>	combinatorics	always

Domain: Collections

Definition

Epsil, as the implementation runs it.

count(_n)

_tables[_n + 1]

unrank(_n, _r)

Drop(
      Fold(Function(
                     Apply(
                            (zb: integer) => Join(
                                                   [zs[1] - zb],
                                                   Drop(zs, 1),
                                                   [1],
                                                 ) if zs[1] >= zb else Join(
                                                                            [zs[1]],
                                                                            Drop(zs, 1),
                                                                            [0],
                                                                          ),
                            _tables[(_n - zj) * 1 + 0 + 1],
                          ),
                     zs,
                     zj,
                   ), [_r], Range(1, _n, 1)),
      1,
    )

rank(_n, _x)

Fold(Function(
               acc + (_tables[(_n - j) * 1 + 0 + 1] if _x[j] == 1 else 0),
               acc,
               j,
             ), 0, Range(1, _n, 1))

valid(_n, _x)

Length(_x) == _n && Fold(
                          Function(ok_j && 0 <= _x[j] && _x[j] <= 1, ok_j, j),
                          True,
                          Range(1, Length(_x), 1),
                        ) && Fold(Function(
                                           ok_w && _x[w - 0] + _x[w - 1] < 2,
                                           ok_w,
                                           w,
                                         ), True, Range(2, Length(_x), 1))

tables(_n)

Fold(
      Function(
                Join(fw_t, Fold(
                                 Function(
                                           ReplaceAt(
                                                      fw_row,
                                                      fw_c + 1,
                                                      fw_t[(fw_s - 1) * 1 + 0 +
                                                           1] +
                                                      (fw_t[(fw_s - 2) * 1 +
                                                            0 + 1] if fw_s >= 2 else 1),
                                                    ),
                                           fw_row,
                                           fw_c,
                                         ),
                                 Map(Function(0, fw_z), Range(0, 1 - 1, 1)),
                                 Range(0, 1 - 1, 1),
                               )),
                fw_t,
                fw_s,
              ),
      Fold(
            Function(ReplaceAt(fw_row, fw_c + 1, 1), fw_row, fw_c),
            Map(Function(0, fw_z), Range(0, 1 - 1, 1)),
            Range(0, 1 - 1, 1),
          ),
      Range(1, _n + 1 - 1, 1),
    )

Examples

Basic #

$F(7) = 13$

live ↗

In$\mathrm{Count}(\mathrm{FibonacciWords}(5))$Out$13$

Length 3, no two adjacent 1s

live ↗

In$\mathrm{Take}(\mathrm{FibonacciWords}(3), 5)$Out$\bigl\lbrack\bigl\lbrack0, 0, 0\bigr\rbrack, \bigl\lbrack0, 0, 1\bigr\rbrack, \bigl\lbrack0, 1, 0\bigr\rbrack, \bigl\lbrack1, 0, 0\bigr\rbrack, \bigl\lbrack1, 0, 1\bigr\rbrack\bigr\rbrack$

About

Examples	2
Crosswalk	OEIS ×5

See also: BinaryStrings, SubsetsWithoutConsecutive