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

Author

Gus Wiseman, Aug 05 2023

Keywords

• nonn

Examples

			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}
		

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.

Programs

Mathematica

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

Formula

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

Extensions

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