A095941 Number of subsets of {1,2,...,n} such that every number in the set is no larger than the sum of the other numbers in the set.

0, 0, 1, 4, 13, 35, 85, 194, 425, 904, 1885, 3878, 7904, 16008, 32282, 64913, 130280, 261145, 523036, 1047017, 2095222, 4191927, 8385695, 16773663, 33550117, 67103645, 134211440, 268427907, 536861880, 1073731053, 2147470842, 4294952115, 8589916646, 17179848025

Offset: 1

Author

Michael Rieck and W. Edwin Clark, Jul 13 2004

Keywords

• nonn
• nice
• easy

Comments

These are the lengths of the sides of a (possibly degenerate) polygon.

Might be called "coalition sets": no member of the set can outnumber all of the others, so a coalition is needed in order to get a majority. - Jaap Spies, Jul 14 2004

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..3321 (first 500 terms from T. D. Noe)

Crossrefs

See A095944 for formula. Cf. A002623.

Programs

Maple

b:= proc(n, s) option remember; `if`(s<1, 2^n,
     `if`(n*(n+1)/2 add(b(j-1, j), j=1..n):
seq(a(n), n=1..37);  # Alois P. Heinz, Feb 13 2021

Mathematica

max = 30; -Accumulate[ Accumulate[q = PartitionsQ[ Range[max]]] + 1] + Accumulate[q] + 2^Range[max] - 1 (* Jean-François Alcover, Aug 01 2013, after A095944 *)

Extensions

Extended by Alexander D. Healy using data from A095944, Nov 18 2005