A364463 Number of subsets of {1..n} with elements disjoint from first differences of elements.

1, 2, 3, 6, 10, 18, 30, 54, 92, 167, 290, 525, 935, 1704, 3082, 5664, 10386, 19249, 35701, 66702, 124855, 234969, 443174, 839254, 1592925, 3032757, 5786153, 11066413, 21204855, 40712426, 78294085, 150815154, 290922900, 561968268, 1086879052, 2104570243

Offset

0,2

Comments

In other words, no element is the difference of two consecutive elements.

From David A. Corneth, Aug 02 2023: (Start)

As subsets counted in a(n) are also counted in a(n+1) and {n+1} is a subset counted in a(n+1) but not a(n), a(n + 1) > a(n) for n >= 1.

As every subset counted in a(n + 1) that contains n+1 can be found from some subset counted in a(n) by appending n+1 and every subset counted in a(n) not containing n + 1 is counted in a(n + 1), a(n+1) <= 2*a(n). (End)

Links

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

Formula

a(n) < a(n + 1) <= 2 * a(n). - David A. Corneth, Aug 02 2023

Example

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

Mathematica

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

Prog

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

Crossrefs

For all differences of pairs of elements we have A007865.

For partitions instead of subsets we have A363260, strict A364464.

The complement is counted by A364466.

A000041 counts integer partitions, strict A000009.

A364465 counts subsets with distinct first differences, partitions A325325.

Cf. A011782, A025065, A229816, A236912, A237113, A237667, A240861, A320347, A323092, A326083, A364347.

Sequence in context: A121364 A347787 A215006 * A172516 A102702 A077930

Adjacent sequences: A364460 A364461 A364462 * A364464 A364465 A364466

Keyword

nonn

Author

Gus Wiseman, Jul 27 2023

Extensions

a(21)-a(29) from David A. Corneth, Aug 02 2023

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

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

Status

approved