A364672 Number of subsets of {1..n} not containing all of their own first differences.

0, 0, 0, 2, 6, 18, 41, 94, 198, 416, 853, 1746, 3531, 7151, 14415, 29049, 58431, 117528, 236145, 474436, 952627, 1912494, 3838175, 7701540, 15449676, 30988137, 62142415, 124600422, 249795358, 500719994, 1003575768, 2011211100, 4030123185, 8074898552, 16177657763, 32408393211, 64917907623

Offset

0,4

Links

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

Formula

a(n) = 2^n - A364671(n). - Andrew Howroyd, Jan 27 2024

Example

The a(0) = 0 through a(5) = 18 subsets:
  .  .  .  {1,3}  {1,3}    {1,3}
           {2,3}  {1,4}    {1,4}
                  {2,3}    {1,5}
                  {3,4}    {2,3}
                  {1,3,4}  {2,5}
                  {2,3,4}  {3,4}
                           {3,5}
                           {4,5}
                           {1,2,5}
                           {1,3,4}
                           {1,3,5}
                           {1,4,5}
                           {2,3,4}
                           {2,3,5}
                           {2,4,5}
                           {3,4,5}
                           {1,3,4,5}
                           {2,3,4,5}

Mathematica

Table[Length[Select[Subsets[Range[n]], !SubsetQ[#, Differences[#]]&]], {n, 0, 10}]

Crossrefs

For disjunction instead of containment we have A364463, partitions A363260.

For overlap we have A364466, partitions A364467 (strict A364536).

The complement is counted by A364671, partitions A364673, A364674, A364675.

First differences of terms are A364753, complement A364752.

Cf. A007862, A054519, A151897, A237667, A325325, A326083, A363225, A364345, A364464, A364537.

Sequence in context: A338765 A339149 A101695 * A014741 A016059 A291519

Adjacent sequences: A364669 A364670 A364671 * A364673 A364674 A364675

Keyword

nonn

Author

Gus Wiseman, Aug 05 2023

Extensions

a(21) onwards (using A364671) added by Andrew Howroyd, Jan 27 2024

Status

approved