SubsetsWithoutConsecutive

The subsets of $\{1, \dots, n\}$ containing no two consecutive integers. Count is the Fibonacci number $F(n+2)$.

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

SubsetsWithoutConsecutive(n)subsets of $\{1, \dots, n\}$ with no two consecutive elements

Typed signatures

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

Domain: Collections

Definition

Epsil, as the implementation runs it.

count(_n)

Fold(
      Function(gc + (Binomial(_n - gn + 1, gn) if True else 0), gc, gn),
      0,
      Range(0, _n, 1),
    )

unrank(_n, _r)

Apply(
       (gp: list<integer>) => Apply(
                                     (gm: list<integer>) => Map(
                                                                 Function(gm[gi] +
                                                                          (gi -
                                                                           1), gi),
                                                                 Range(
                                                                        1,
                                                                        Length(gm),
                                                                        1,
                                                                      ),
                                                               ),
                                     Rest(Fold(
                                                Function(Apply(
                                                                (lc: list<integer>) => Join([lc[1]], Rest(ls_g), [lc[2]]),
                                                                Fold(
                                                                      Function(
                                                                                lp_g if lp_g[2] != 0 ||
                                                                                        lv_g <=
                                                                                        (0 if lj_g == 1 else ls_g[lj_g]) else [lp_g[1], lv_g] if lp_g[1] <
                                                                                                                 Binomial(_n - gp[2] +
                                                                                                                          1 -
                                                                                                                          lv_g, gp[2] - lj_g) else [lp_g[1] -
                                                                                                                        Binomial(_n - gp[2] +
                                                                                                                                 1 -
                                                                                                                                 lv_g, gp[2] - lj_g), 0],
                                                                                lp_g,
                                                                                lv_g,
                                                                              ),
                                                                      [
                                                                        ls_g[1],
                                                                        0,
                                                                      ],
                                                                      Range(
                                                                             1,
                                                                             _n -
                                                                             gp[2] +
                                                                             1,
                                                                             1,
                                                                           ),
                                                                    ),
                                                              ), ls_g, lj_g),
                                                [gp[1]],
                                                Range(1, gp[2], 1),
                                              )),
                                   ),
       Fold(
             Function(gs if gs[2] >= 0 else [gs[1], gk] if gs[1] <
                                                           (Binomial(
                                                                      _n - gk +
                                                                      1,
                                                                      gk,
                                                                    ) if True else 0) else [gs[1] -
                                                                  (Binomial(
                                                                             _n -
                                                                             gk +
                                                                             1,
                                                                             gk,
                                                                           ) if True else 0), -1], gs, gk),
             [_r, -1],
             Range(0, _n, 1),
           ),
     )

rank(_n, _x)

Apply(
       (gy: list<integer>) => Fold(Function(gb +
                                            (Binomial(_n - gt + 1, gt) if True else 0), gb, gt), 0, Range(0, Length(_x) -
                                                                   1, 1)) + Fold(
                                                                                 Function(kr +
                                                                                          Fold(
                                                                                                Function(kq +
                                                                                                         Binomial(_n - Length(_x) +
                                                                                                                  1 -
                                                                                                                  kv, Length(_x) - kj), kq, kv),
                                                                                                0,
                                                                                                Range((0 if kj == 1 else gy[kj - 1]) +
                                                                                                      1, gy[kj] - 1, 1),
                                                                                              ), kr, kj),
                                                                                 0,
                                                                                 Range(1, Length(_x), 1),
                                                                               ),
       Apply((gx: list<integer>) => Map(
                                         Function(gx[gi] - (gi - 1), gi),
                                         Range(1, Length(_x), 1),
                                       ), Sort(_x)),
     )

valid(_n, _x)

Fold(Function(
               (ReplaceAt(dm_seen, _x[dm_j], 1) if dm_seen[_x[dm_j]] == 0 else ReplaceAt(
                                                                                          dm_seen,
                                                                                          _n + 1,
                                                                                          1,
                                                                                        )) if 1 <= _x[dm_j] &&
                                                                                             _x[dm_j] <= _n else ReplaceAt(dm_seen, _n + 1, 1),
               dm_seen,
               dm_j,
             ), Map(Function(0, dm_z), Range(1, _n + 1, 1)), Range(
                                                                   1,
                                                                   Length(_x),
                                                                   1,
                                                                 ))[_n + 1] == 0 &&
True && Apply(
               (gz: list<integer>) => Fold(
                                            Function(ok_ga && gz[ga] -
                                                              gz[ga - 1] > 1, ok_ga, ga),
                                            True,
                                            Range(2, Length(_x), 1),
                                          ),
               Sort(_x),
             )

Examples

Basic #

$F(7) = 13$

live ↗

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

No two consecutive integers

live ↗

In$\mathrm{Take}(\mathrm{SubsetsWithoutConsecutive}(3), 5)$Out$\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack1\bigr\rbrack, \bigl\lbrack2\bigr\rbrack, \bigl\lbrack3\bigr\rbrack, \bigl\lbrack1, 3\bigr\rbrack\bigr\rbrack$

About

Examples	2
Crosswalk	OEIS ×5

See also: Subsets, FibonacciWords