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

0, 0, 0, 0, 0, 1, 7, 23, 46, 113, 287, 680, 1546, 3374, 7191, 15008, 30016, 61013, 124354, 252577, 511229, 1031064, 2074281, 4164716, 8350912, 16729473, 33494928, 67034995, 134127390, 268325204, 536737665, 1073581062, 2147162124, 4294458549, 8589210382, 17178890873

Offset: 0

Author

Gus Wiseman, Mar 10 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(7) = 23 subsets:
  .  .  .  .  .  {2,3,4,5}  {2,4,6}      {2,4,6}
                            {2,3,4,5}    {2,3,4,5}
                            {2,3,4,6}    {2,3,4,6}
                            {2,3,5,6}    {2,3,4,7}
                            {2,4,5,6}    {2,3,5,6}
                            {3,4,5,6}    {2,3,5,7}
                            {2,3,4,5,6}  {2,3,6,7}
                                         {2,4,5,6}
                                         {2,4,5,7}
                                         {2,4,6,7}
                                         {2,5,6,7}
                                         {3,4,5,6}
                                         {3,4,5,7}
                                         {3,4,6,7}
                                         {3,5,6,7}
                                         {4,5,6,7}
                                         {2,3,4,5,6}
                                         {2,3,4,5,7}
                                         {2,3,4,6,7}
                                         {2,3,5,6,7}
                                         {2,4,5,6,7}
                                         {3,4,5,6,7}
                                         {2,3,4,5,6,7}
		

Crossrefs

The case with ones allowed is A370637, differences A370589.

The minimal case is A370644, with ones A370642.

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.

Cf. A072639, A326031, A355740, A367905, A368109.

Cf. A133686, A140637, A355529, A367867, A370583, A370636, A370640.

Programs

Mathematica

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

Extensions

More terms from Jinyuan Wang, Mar 28 2025