login
A364463
Number of subsets of {1..n} with elements disjoint from first differences of elements.
15
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)
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.
Sequence in context: A121364 A347787 A215006 * A172516 A102702 A077930
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