A370642 Number of minimal subsets of {1..n} such that it is not possible to choose a different binary index of each element.

0, 0, 0, 1, 1, 3, 9, 26, 26, 40, 82, 175, 338, 636, 1114

Offset

0,6

Comments

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

Links

Table of n, a(n) for n=0..14.

Example

The a(0) = 0 through a(6) = 9 subsets:
  .  .  .  {1,2,3}  {1,2,3}  {1,2,3}    {1,2,3}
                             {1,4,5}    {1,4,5}
                             {2,3,4,5}  {2,4,6}
                                        {1,2,5,6}
                                        {1,3,4,6}
                                        {1,3,5,6}
                                        {2,3,4,5}
                                        {2,3,5,6}
                                        {3,4,5,6}

Mathematica

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
fasmin[y_]:=Complement[y, Union@@Table[Union[s, #]& /@ Rest[Subsets[Complement[Union@@y, s]]], {s, y}]];
Table[Length[fasmin[Select[Subsets[Range[n]], Select[Tuples[bpe/@#], UnsameQ@@#&]=={}&]]], {n, 0, 10}]

Crossrefs

For prime indices we have A370591, minima of A370583, complement A370582.

This is the minimal case of A370637, complement A370636.

The version for a unique choice is A370638, maxima A370640, diffs A370641.

The case without ones is A370644.

A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.

A070939 gives length of binary expansion.

A096111 gives product of binary indices.

A326031 gives weight of the set-system with BII-number n.

A367902 counts choosable set-systems, ranks A367906, unlabeled A368095.

A367903 counts non-choosable set-systems, ranks A367907, unlabeled A368094.

A368100 ranks choosable multisets, complement A355529.

A370585 counts maximal choosable sets.

Cf. A072639, A140637, A367905, A368109, A370589, A370593, A370639.

Sequence in context: A119851 A119825 A235538 * A358915 A218916 A037260

Adjacent sequences: A370639 A370640 A370641 * A370643 A370644 A370645

Keyword

nonn,more

Author

Gus Wiseman, Mar 10 2024

Status

approved