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

0, 0, 0, 0, 0, 1, 4, 13, 13, 26, 56, 126, 243, 471, 812, 1438

Offset

0,7

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..15.

Example

The a(0) = 0 through a(7) = 13 subsets:
  .  .  .  .  .  {2,3,4,5}  {2,4,6}    {2,4,6}
                            {2,3,4,5}  {2,3,4,5}
                            {2,3,5,6}  {2,3,4,7}
                            {3,4,5,6}  {2,3,5,6}
                                       {2,3,5,7}
                                       {2,3,6,7}
                                       {2,4,5,7}
                                       {2,5,6,7}
                                       {3,4,5,6}
                                       {3,4,5,7}
                                       {3,4,6,7}
                                       {3,5,6,7}
                                       {4,5,6,7}
The a(0) = 0 through a(7) = 13 set-systems:
  .  .  .  .  .  {2}{12}{3}{13}  {2}{3}{23}       {2}{3}{23}
                                 {2}{12}{3}{13}   {2}{12}{3}{13}
                                 {12}{3}{13}{23}  {12}{3}{13}{23}
                                 {2}{12}{13}{23}  {2}{12}{13}{23}
                                                  {2}{12}{3}{123}
                                                  {2}{3}{13}{123}
                                                  {12}{3}{13}{123}
                                                  {12}{3}{23}{123}
                                                  {2}{12}{13}{123}
                                                  {2}{12}{23}{123}
                                                  {2}{13}{23}{123}
                                                  {3}{13}{23}{123}
                                                  {12}{13}{23}{123}

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[2, n]], Select[Tuples[bpe/@#], UnsameQ@@#&]=={}&]]], {n, 0, 10}]

Crossrefs

The version with ones allowed is A370642, minimal case of A370637.

This is the minimal case of A370643.

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

A070939 gives length of binary expansion.

A096111 gives product of binary indices.

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

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

A370585 counts maximal choosable sets.

Cf. A072639, A140637, A326031, A355529, A367905, A368109, A370589, A370591, A370636, A370639, A370640.

Sequence in context: A301792 A344512 A168401 * A081738 A232496 A239256

Adjacent sequences: A370641 A370642 A370643 * A370645 A370646 A370647

Keyword

nonn,more

Author

Gus Wiseman, Mar 11 2024

Status

approved