A370819 Number of subsets of {1..n-1} whose cardinality is one less than the length of the binary expansion of n; a(0) = 0.

0, 1, 1, 2, 3, 6, 10, 15, 35, 56, 84, 120, 165, 220, 286, 364, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 169911, 201376, 237336, 278256, 324632, 376992, 435897, 501942, 575757, 658008, 749398, 850668

Offset

0,4

Links

Table of n, a(n) for n=0..43.

Formula

a(n) = binomial(n - 1, A029837(n+1) - 1) = binomial(n - 1, A113473(n) - 1) = binomial(n - 1, A070939(n) - 1) for n > 0.

Example

The a(1) = 1 through a(7) = 15 subsets:
  {}  {1}  {1}  {1,2}  {1,2}  {1,2}  {1,2}
           {2}  {1,3}  {1,3}  {1,3}  {1,3}
                {2,3}  {1,4}  {1,4}  {1,4}
                       {2,3}  {1,5}  {1,5}
                       {2,4}  {2,3}  {1,6}
                       {3,4}  {2,4}  {2,3}
                              {2,5}  {2,4}
                              {3,4}  {2,5}
                              {3,5}  {2,6}
                              {4,5}  {3,4}
                                     {3,5}
                                     {3,6}
                                     {4,5}
                                     {4,6}
                                     {5,6}

Mathematica

Table[If[n==0, 0, Binomial[n-1, IntegerLength[n, 2]-1]], {n, 0, 15}]

Crossrefs

The version without subtracting one is A357812.

Dominates A370641, see also A370640.

A007318 counts subsets by cardinality.

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. A029837, A113473, A326031, A367905, A368109, A370636.

Sequence in context: A268064 A077011 A246868 * A055789 A238891 A048681

Adjacent sequences: A370816 A370817 A370818 * A370820 A370821 A370822

Keyword

nonn

Author

Gus Wiseman, Mar 11 2024

Status

approved