A370638 Number of subsets of {1..n} such that a unique set can be obtained by choosing a different binary index of each element.

1, 2, 4, 6, 12, 19, 30, 45, 90, 147, 230, 343, 504, 716, 994, 1352, 2704, 4349, 6469, 9162, 12585, 16862, 22122, 28617, 36653, 46431, 58075, 72097, 88456, 107966, 130742, 157647, 315294, 494967, 704753, 950080, 1234301, 1565165, 1945681, 2387060, 2890368, 3470798

Offset: 0

Author

Gus Wiseman, Mar 09 2024

Keywords

• nonn

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.

Examples

			The set {3,4} has binary indices {{1,2},{3}}, with two choices {1,3}, {2,3}, so is not counted under a(4).
The a(0) = 1 through a(5) = 19 subsets:
  {}  {}   {}     {}     {}       {}
      {1}  {1}    {1}    {1}      {1}
           {2}    {2}    {2}      {2}
           {1,2}  {1,2}  {4}      {4}
                  {1,3}  {1,2}    {1,2}
                  {2,3}  {1,3}    {1,3}
                         {1,4}    {1,4}
                         {2,3}    {1,5}
                         {2,4}    {2,3}
                         {1,2,4}  {2,4}
                         {1,3,4}  {4,5}
                         {2,3,4}  {1,2,4}
                                  {1,2,5}
                                  {1,3,4}
                                  {1,3,5}
                                  {2,3,4}
                                  {2,3,5}
                                  {2,4,5}
                                  {3,4,5}
		

Links

• Wikipedia, Axiom of choice.

Crossrefs

Set systems of this type are counted by A367904, ranks A367908.

A version for MM-numbers of multisets is A368101.

For prime indices we have A370584.

This is the unique version of A370636, complement A370637.

The maximal case is A370640, differences A370641.

Factorizations of this type are counted by A370645.

The case A370818 is the restriction to A000225.

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

A058891 counts set-systems, A003465 covering, A323818 connected.

A070939 gives length of binary expansion.

A096111 gives product of binary indices.

Cf. A133686, A134964, A326031, A326702, A367772, A367867, A367905, A367909, A367912, A368109.

Programs

Mathematica

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

Formula

a(2^n - 1) = A370818(n).

Extensions

More terms from Jinyuan Wang, Mar 28 2025