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

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(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}
		

Links

• Wikipedia, Axiom of choice.

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.

Programs

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}]

Formula

First differences of A370636.

Extensions

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