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

0, 0, 0, 1, 2, 8, 25, 67, 134, 309, 709, 1579, 3420, 7240, 15077, 30997, 61994, 125364, 253712, 512411, 1032453, 2075737, 4166469, 8352851, 16731873, 33497422, 67038086, 134130344, 268328977, 536741608, 1073586022, 2147296425, 4294592850, 8589346462, 17179033384

Offset: 0

Author

Gus Wiseman, Mar 08 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 a(0) = 0 through a(5) = 8 subsets:
  .  .  .  {1,2,3}  {1,2,3}    {1,2,3}
                    {1,2,3,4}  {1,4,5}
                               {1,2,3,4}
                               {1,2,3,5}
                               {1,2,4,5}
                               {1,3,4,5}
                               {2,3,4,5}
                               {1,2,3,4,5}
		

Links

• Wikipedia, Axiom of choice.
• Gus Wiseman, Statistics, classes, and transformations of standard compositions

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 A370582, differences A370586.

For prime indices we have A370583, differences A370587.

First differences are A370589.

The complement is counted by A370636, differences A370639.

The case without ones is A370643.

The version for a unique choice is A370638, maxima A370640, diffs A370641.

The minimal case 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, A072639, A355739, A355740, A367772, A367905, A367909, A367912, A368094, A368095, A368109.

Programs

Mathematica

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

Formula

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

Partial sums of A370589.

Extensions

a(21)-a(34) from Alois P. Heinz, Mar 09 2024