cp's OEIS Frontend

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

%I A370637 #11 Mar 09 2024 15:28:33
%S A370637 0,0,0,1,2,8,25,67,134,309,709,1579,3420,7240,15077,30997,61994,
%T A370637 125364,253712,512411,1032453,2075737,4166469,8352851,16731873,
%U A370637 33497422,67038086,134130344,268328977,536741608,1073586022,2147296425,4294592850,8589346462,17179033384
%N A370637 Number of subsets of {1..n} such that it is not possible to choose a different binary index of each element.
%C A370637 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.
%H A370637 Wikipedia, <a href="https://en.wikipedia.org/wiki/Axiom_of_choice">Axiom of choice</a>.
%H A370637 Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vTCPiJVFUXN8IqfLlCXkgP15yrGWeRhFS4ozST5oA4Bl2PYS-XTA3sGsAEXvwW-B0ealpD8qnoxFqN3/pub">Statistics, classes, and transformations of standard compositions</a>
%F A370637 a(2^n - 1) = A367903(n).
%F A370637 Partial sums of A370589.
%e A370637 The a(0) = 0 through a(5) = 8 subsets:
%e A370637   .  .  .  {1,2,3}  {1,2,3}    {1,2,3}
%e A370637                     {1,2,3,4}  {1,4,5}
%e A370637                                {1,2,3,4}
%e A370637                                {1,2,3,5}
%e A370637                                {1,2,4,5}
%e A370637                                {1,3,4,5}
%e A370637                                {2,3,4,5}
%e A370637                                {1,2,3,4,5}
%t A370637 bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
%t A370637 Table[Length[Select[Subsets[Range[n]], Select[Tuples[bpe/@#],UnsameQ@@#&]=={}&]],{n,0,10}]
%Y A370637 Simple graphs not of this type are counted by A133686, covering A367869.
%Y A370637 Unlabeled graphs of this type are counted by A140637, complement A134964.
%Y A370637 Simple graphs of this type are counted by A367867, covering A367868.
%Y A370637 Set systems not of this type are counted by A367902, ranks A367906.
%Y A370637 Set systems of this type are counted by A367903, ranks A367907.
%Y A370637 Set systems uniquely not of this type are counted by A367904, ranks A367908.
%Y A370637 Unlabeled multiset partitions of this type are A368097, complement A368098.
%Y A370637 A version for MM-numbers of multisets is A355529, complement A368100.
%Y A370637 Factorizations are counted by A368413/A370813, complement A368414/A370814.
%Y A370637 The complement for prime indices is A370582, differences A370586.
%Y A370637 For prime indices we have A370583, differences A370587.
%Y A370637 First differences are A370589.
%Y A370637 The complement is counted by A370636, differences A370639.
%Y A370637 The case without ones is A370643.
%Y A370637 The version for a unique choice is A370638, maxima A370640, diffs A370641.
%Y A370637 The minimal case is A370642, without ones A370644.
%Y A370637 A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
%Y A370637 A058891 counts set-systems, A003465 covering, A323818 connected.
%Y A370637 A070939 gives length of binary expansion.
%Y A370637 A096111 gives product of binary indices.
%Y A370637 A326031 gives weight of the set-system with BII-number n.
%Y A370637 Cf. A000612, A072639, A355739, A355740, A367772, A367905, A367909, A367912, A368094, A368095, A368109.
%K A370637 nonn
%O A370637 0,5
%A A370637 _Gus Wiseman_, Mar 08 2024
%E A370637 a(21)-a(34) from _Alois P. Heinz_, Mar 09 2024