login
A367400
Number of subsets of {1..n} whose cardinality is not the sum of two distinct elements.
8
1, 2, 4, 7, 13, 25, 47, 88, 166, 313, 589, 1109, 2089, 3934, 7408, 13951, 26273, 49477, 93175, 175468, 330442, 622289, 1171897, 2206921, 4156081, 7826746, 14739356, 27757207, 52272469, 98439697, 185381983, 349112000, 657448942, 1238110153
OFFSET
0,2
FORMULA
Conjectures from Chai Wah Wu, Nov 21 2023: (Start)
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) for n > 3.
G.f.: (-x^3 + x^2 + 1)/(x^4 - 2*x^3 + x^2 - 2*x + 1). (End)
EXAMPLE
The set s = {1,2,3,6,7,8} has the following sums of pairs of distinct elements: {3,4,5,7,8,9,10,11,13,14,15}. This does not include 6, so s is counted under a(8).
The a(0) = 1 through a(4) = 13 subsets:
{} {} {} {} {}
{1} {1} {1} {1}
{2} {2} {2}
{1,2} {3} {3}
{1,2} {4}
{1,3} {1,2}
{2,3} {1,3}
{1,4}
{2,3}
{2,4}
{3,4}
{1,3,4}
{2,3,4}
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#, {2}], Length[#]]&]], {n, 0, 10}]
PROG
(Python)
from itertools import combinations
def A367400(n): return (n*(n+1)>>1)+1+sum(1 for k in range(3, n+1) for w in (set(d) for d in combinations(range(1, n+1), k)) if not any({a, k-a}<=w for a in range(1, k+1>>1))) # Chai Wah Wu, Nov 21 2023
CROSSREFS
The version containing n appears to be A112575.
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free semi-full semi-free
-----------------------------------------------------------
A002865 counts partitions whose length is a part, complement A229816.
A364534 counts sum-full subsets.
A088809 and A093971 count subsets containing semi-sums.
A236912 counts partitions with no semi-sum of the parts, ranks A364461.
A366738 counts semi-sums of partitions, strict A366741.
Triangles:
A365381 counts subsets with a subset summing to k, complement A366320.
A365541 counts subsets with a semi-sum k.
A367404 counts partitions with a semi-sum k, strict A367405.
Sequence in context: A079958 A224341 A235684 * A018082 A018083 A108361
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Nov 21 2023
EXTENSIONS
a(18)-a(33) from Chai Wah Wu, Nov 21 2023
STATUS
approved