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,4

Comments

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

Links

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

Formula

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

Example

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}

Mathematica

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

Prog

(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

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.

Sequence in context: A184697 A124613 A296626 * A124614 A070933 A059570

Adjacent sequences: A364463 A364464 A364465 * A364467 A364468 A364469

Keyword

nonn

Author

Gus Wiseman, Jul 31 2023

Extensions

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

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

Status

approved