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

0, 0, 0, 1, 1, 6, 17, 42, 67, 175, 400, 870, 1841, 3820, 7837, 15920, 30997, 63370, 128348, 258699, 520042, 1043284, 2090732, 4186382, 8379022, 16765549, 33540664, 67092258, 134198633, 268412631, 536844414, 1073710403, 2147296425, 4294753612, 8589686922, 17179580003

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

Wikipedia, Axiom of choice.

Example

The binary indices of {1,4,5} are {{1},{3},{1,3}}, from which it is not possible to choose three different elements, so S is counted under a(3).
The binary indices of S = {1,6,8,9} are {{1},{2,3},{4},{1,4}}, from which it is not possible to choose four different elements, so S is counted under a(9).
The a(0) = 0 through a(6) = 17 subsets:
  .  .  .  {1,2,3}  {1,2,3,4}  {1,4,5}      {2,4,6}
                               {1,2,3,5}    {1,2,3,6}
                               {1,2,4,5}    {1,2,4,6}
                               {1,3,4,5}    {1,2,5,6}
                               {2,3,4,5}    {1,3,4,6}
                               {1,2,3,4,5}  {1,3,5,6}
                                            {1,4,5,6}
                                            {2,3,4,6}
                                            {2,3,5,6}
                                            {2,4,5,6}
                                            {3,4,5,6}
                                            {1,2,3,4,6}
                                            {1,2,3,5,6}
                                            {1,2,4,5,6}
                                            {1,3,4,5,6}
                                            {2,3,4,5,6}
                                            {1,2,3,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 not of this type are counted by A133686, covering A367869.

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

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

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

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

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

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

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

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

The complement for prime indices is A370586, differences of A370582.

For prime indices we have A370587, differences of A370583.

Partial sums are A370637/A370643, minima A370642/A370644.

The complement is counted by A370639, partial sums A370636.

The version for a unique choice is A370641, partial sums 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, A072639, A326702, A355739, A355740, A367772, A367905, A367909, A367912, A368094, A368095, A368109, A370640.

Sequence in context: A220407 A013319 A047861 * A343518 A365409 A171507

Adjacent sequences: A370586 A370587 A370588 * A370590 A370591 A370592

Keyword

nonn

Author

Gus Wiseman, Mar 08 2024

Extensions

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

Status

approved