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

1, 2, 4, 7, 14, 24, 39, 61, 122, 203, 315, 469, 676, 952, 1307, 1771, 3542, 5708, 8432, 11877, 16123, 21415, 27835, 35757, 45343, 57010, 70778, 87384, 106479, 129304, 155802, 187223, 374446, 588130, 835800, 1124981, 1456282, 1841361, 2281772, 2791896, 3367162

Offset

0,2

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

Wikipedia, Axiom of choice.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

Formula

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

Partial sums of A370639.

Example

The a(0) = 1 through a(4) = 14 subsets:
  {}  {}   {}     {}     {}
      {1}  {1}    {1}    {1}
           {2}    {2}    {2}
           {1,2}  {3}    {3}
                  {1,2}  {4}
                  {1,3}  {1,2}
                  {2,3}  {1,3}
                         {1,4}
                         {2,3}
                         {2,4}
                         {3,4}
                         {1,2,4}
                         {1,3,4}
                         {2,3,4}

Mathematica

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

Crossrefs

Simple graphs of this type are counted by A133686, covering A367869.

Unlabeled graphs of this type are counted by A134964, complement A140637.

Simple graphs not of this type are counted by A367867, covering A367868.

Set systems of this type are counted by A367902, ranks A367906.

Set systems not of this type are counted by A367903, ranks A367907.

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

Unlabeled multiset partitions of this type are A368098, complement A368097.

A version for MM-numbers of multisets is A368100, complement A355529.

Factorizations are counted by A368414/A370814, complement A368413/A370813.

For prime indices we have A370582, differences A370586.

The complement for prime indices is A370583, differences A370587.

The complement is A370637, differences A370589, without ones A370643.

The case of a unique choice is A370638, maxima A370640, differences A370641.

First differences are A370639.

The minimal case of the complement is A370642, without ones A370644.

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.

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

Cf. A000612, A326702, A355739, A355740, A367772, A367905, A367909, A367912, A368095, A368109.

Sequence in context: A000075 A285903 A048248 * A056180 A000076 A217730

Adjacent sequences: A370633 A370634 A370635 * A370637 A370638 A370639

Keyword

nonn

Author

Gus Wiseman, Mar 08 2024

Extensions

a(19)-a(40) from Alois P. Heinz, Mar 09 2024

Status

approved