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.

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

Author

Henry Bottomley, Feb 13 2021

Keywords

• nonn

Comments

In other words, every element of S is strictly less than half the sum.

Examples

			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}.
		

Links

• math.stackexchange, Permutation and Combinatorics Problem

Crossrefs

Cf. A000009, A002623, A095941, A095944, A317910.

Programs

Maple

b:= proc(n, s) option remember; `if`(s<1, 2^n,
     `if`(n*(n+1)/2 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 *)

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).