OFFSET

1,2

COMMENTS

LINKS

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

FORMULA

Second differences are A000009, partitions into distinct parts. Proof from Fred W. Helenius (fredh(AT)ix.netcom.com): Let k be the largest element (the "dictator") in S and let j be the sum of the remaining elements, so 0 <= j < k. For a given k and j, the number of subsets S is just the number of partitions j into distinct parts; call that a(j). Then b(n) = Sum_{1<=k<=n} Sum_{0<=j<k} a(j). This was independently discovered by N. J. A. Sloane and proved by Michael Reid.

a(n) ~ 3^(3/4) * n^(1/4) * exp(sqrt(n/3)*Pi) / Pi^2. - Vaclav Kotesovec, Mar 12 2016

G.f.: (x/(1 - x)^2)*Product_{k>=1} (1 + x^k). - Ilya Gutkovskiy, Jan 03 2017

EXAMPLE

a(3) = 6 since the subsets {1},{2},{3},{1,2},{1,3},{2,3} are the only subsets of {1,2,3} which contain a number greater than the sum of the other numbers in the set.

MATHEMATICA

r[s_, x_] := r[s, x] = 1 + Sum[r[s-i, i-1], {i, Min[x, s]}]; f[n_] := Sum[r[k-1, k-1], {k, n}]; Array[f, 50] (* Giovanni Resta, Mar 16 2006 *)

Accumulate[ Accumulate[q = PartitionsQ[ Range[1, 50]]]+1] - Accumulate[q] (* Jean-François Alcover, Nov 14 2011 *)

CROSSREFS

KEYWORD

nice,nonn,easy

AUTHOR

W. Edwin Clark, Jul 13 2004

EXTENSIONS

More terms from John W. Layman, Aug 10 2004

More terms from Giovanni Resta, Mar 16 2006

STATUS

approved