login
A364466
Number of subsets of {1..n} where some element is a difference of two consecutive elements.
13
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.
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.
Sequence in context: A184697 A124613 A296626 * A124614 A070933 A059570
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