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

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)

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), 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 *)

Crossrefs

See A095944 for formula. Cf. A002623.

Sequence in context: A057159 A189588 A266357 * A210843 A177155 A189595

Adjacent sequences: A095938 A095939 A095940 * A095942 A095943 A095944

Keyword

nonn,nice,easy

Author

Michael Rieck and W. Edwin Clark, Jul 13 2004

Extensions

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

Status

approved