

A095944


Number of subsets S of {1,2,...,n} which contain a number that is greater than the sum of the other numbers in S.


8



1, 3, 6, 11, 18, 28, 42, 61, 86, 119, 162, 217, 287, 375, 485, 622, 791, 998, 1251, 1558, 1929, 2376, 2912, 3552, 4314, 5218, 6287, 7548, 9031, 10770, 12805, 15180, 17945, 21158, 24883, 29193, 34171, 39909, 46511, 54095, 62792, 72749, 84132, 97125
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Convolution of A000009 and A001477.  Vaclav Kotesovec, Mar 12 2016


LINKS

T. D. Noe and 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[si, i1], {i, Min[x, s]}]; f[n_] := Sum[r[k1, k1], {k, n}]; Array[f, 50] (* Giovanni Resta, Mar 16 2006 *)
Accumulate[ Accumulate[q = PartitionsQ[ Range[1, 50]]]+1]  Accumulate[q] (* JeanFrançois Alcover, Nov 14 2011 *)


CROSSREFS

Equals 2^n  1  A095941(n).
Sequence in context: A011849 A173690 A178855 * A014284 A118482 A281689
Adjacent sequences: A095941 A095942 A095943 * A095945 A095946 A095947


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



