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

Author

Gus Wiseman, Jul 27 2023

Keywords

• nonn

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)

Examples

			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}
		

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.

Programs

Mathematica

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

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

Formula

a(n) < a(n + 1) <= 2 * a(n). - David A. Corneth, Aug 02 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