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

0, 1, 2, 3, 7, 10, 15, 22, 61, 81, 112, 154, 207, 276, 355, 464, 1771, 2166, 2724, 3445, 4246, 5292, 6420, 7922, 9586, 11667, 13768, 16606, 19095, 22825, 26498, 31421, 187223, 213684, 247670, 289181, 331301, 385079, 440411, 510124, 575266, 662625, 747521

Offset

0,3

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

Wikipedia, Axiom of choice.

Formula

First differences of A370636.

Example

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

Mathematica

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Subsets[Range[n]], MemberQ[#, 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 of this type are A368414/A370814, complement A368413/A370813.

For prime instead of binary indices we have A370586, differences of A370582.

The complement for prime indices is A370587, differences of A370583.

The complement is counted by A370589, differences of A370637.

Partial sums are A370636.

The complement has partial sums A370637/A370643, minima A370642/A370644.

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

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, A367770, A367772, A367905, A367909, A367912, A368094, A368095, A368109, A370640.

Sequence in context: A272649 A266813 A344232 * A361859 A192116 A088163

Adjacent sequences: A370636 A370637 A370638 * A370640 A370641 A370642

Keyword

nonn

Author

Gus Wiseman, Mar 08 2024

Extensions

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

Status

approved