A364466 Number of subsets of {1..n} where some element is a difference of two consecutive elements.

0, 0, 1, 2, 6, 14, 34, 74, 164, 345, 734, 1523, 3161, 6488, 13302, 27104, 55150, 111823, 226443, 457586, 923721, 1862183, 3751130, 7549354, 15184291, 30521675, 61322711, 123151315, 247230601, 496158486, 995447739, 1996668494, 4004044396, 8027966324, 16092990132, 32255168125

Offset: 0

Author

Gus Wiseman, Jul 31 2023

Keywords

• nonn

Comments

In other words, the elements are not disjoint from their own first differences.

Examples

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

Crossrefs

For differences of all pairs we have A093971, complement A196723.

For partitions we have A363260, complement A364467.

The complement is counted by A364463.

For subset-sums instead of differences we have A364534, complement A325864.

For strict partitions we have A364536, complement A364464.

A000041 counts integer partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A050291 counts double-free subsets, complement A088808.

A108917 counts knapsack partitions, strict A275972.

A325325 counts partitions with all distinct differences, strict A320347.

Cf. A011782, A212986, A237113, A325877, A325878, A326083, A363225.

Programs

Mathematica

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

Python

from itertools import combinations
def A364466(n): return sum(1 for l in range(n+1) for c in combinations(range(1,n+1),l) if not set(c).isdisjoint({c[i+1]-c[i] for i in range(l-1)})) # Chai Wah Wu, Sep 26 2023

Formula

a(n) = 2^n - A364463(n). - Chai Wah Wu, Sep 26 2023

Extensions

a(21)-a(32) from Chai Wah Wu, Sep 26 2023

a(33)-a(35) from Chai Wah Wu, Sep 27 2023