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,5

Comments

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

Links

Table of n, a(n) for n=0..34.

math.stackexchange, Permutation and Combinatorics Problem

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

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

Sequence in context: A353017 A183376 A131066 * A058877 A192693 A368217

Adjacent sequences: A341504 A341505 A341506 * A341508 A341509 A341510

Keyword

nonn

Author

Henry Bottomley, Feb 13 2021

Status

approved