login
A341507
Number of nonempty subsets S of {1,2,...,n} in which all elements are strictly less than the sum of the other elements of S.
3
0, 0, 0, 0, 2, 9, 28, 74, 178, 402, 872, 1842, 3821, 7830, 15913, 32161, 64761, 130091, 260911, 522749, 1046667, 2094797, 4191414, 8385079, 16772926, 33549239, 67102603, 134210207, 268426453, 536860171, 1073729049, 2147468499, 4294949383, 8589913467, 17179844335
OFFSET
0,5
COMMENTS
In other words, every element of S is strictly less than half the sum.
FORMULA
a(n) = A095941(n) - A317910(n).
G.f.: (1-x-x^2)/((1-x)^2*(1-2*x)) - (1/(1-x)^2)*Product_{k>=1} (1 + x^k).
EXAMPLE
For n = 5 the a(5)=9 subsets are {2,3,4}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, and {1,2,3,4,5}.
MAPLE
b:= proc(n, s) option remember; `if`(s<1, 2^n,
`if`(n*(n+1)/2<s, 0, b(n-1, s)+b(n-1, max(0, s-n))))
end:
a:= n-> add(b(j-1, j+1), j=1..n):
seq(a(n), n=0..37); # Alois P. Heinz, Feb 13 2021
MATHEMATICA
gf := (1 - x - x^2)/((1 - 2 x) (1 - x)^2) - QPochhammer[-1, x]/(2 (1 - x)^2);
CoefficientList[Series[gf, {x, 0, 34}], x] (* Peter Luschny, Feb 13 2021 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Henry Bottomley, Feb 13 2021
STATUS
approved