EvenSubsets

The subsets of $\{1, \dots, n\}$ of even size: half of Subsets, $2^{n-1}$ of them for $n \ge 1$ .

✓ checked against that system · ! checked, with disagreements (hover a chip)OEISA011782✓A131577✓A000079✓A320487✓A166444✓A034008✓

EvenSubsets(n)the even-size subsets of

\{1, \dots, n\}

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) if gn % 2 == 0 else 0), gc, gn),
      0,
      Range(0, _n, 1),
    )

unrank(_n, _r)

Apply(
       (gp: list<integer>) => Apply(
                                     (gm: list<integer>) => gm,
                                     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 - lv_g, gp[2] - lj_g) else [lp_g[1] -
                                                                                                                        Binomial(_n - lv_g, gp[2] - lj_g), 0],
                                                                                lp_g,
                                                                                lv_g,
                                                                              ),
                                                                      [
                                                                        ls_g[1],
                                                                        0,
                                                                      ],
                                                                      Range(
                                                                             1,
                                                                             _n,
                                                                             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) if gk % 2 ==
                                                                                0 else 0) else [gs[1] -
                                                                  (Binomial(
                                                                             _n,
                                                                             gk,
                                                                           ) if gk %
                                                                               2 ==
                                                                               0 else 0), -1], gs, gk),
             [_r, -1],
             Range(0, _n, 1),
           ),
     )

rank(_n, _x)

Apply((gy: list<integer>) => Fold(Function(
                                            gb + (Binomial(_n, gt) if gt % 2 ==
                                                                      0 else 0),
                                            gb,
                                            gt,
                                          ), 0, Range(0, Length(_x) - 1, 1)) +
                             Fold(Function(
                                            kr + Fold(
                                                       Function(
                                                                 kq +
                                                                 Binomial(
                                                                           _n -
                                                                           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>) => gx, 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 &&
Length(_x) % 2 == 0

Examples

Basic #

$2^{3}$ of the 16 subsets

live ↗

\mathrm{Count}(\mathrm{EvenSubsets}(4))

Out

8

Size 0 and 2 subsets of $\{1,2,3\}$

live ↗

\mathrm{Take}(\mathrm{EvenSubsets}(3), 4)

Out

\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack1, 3\bigr\rbrack, \bigl\lbrack2, 3\bigr\rbrack\bigr\rbrack

About

Examples	2
Crosswalk	OEIS ×6

EvenSubsets ​

Definition

Examples

EvenSubsets