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.

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

Offset

1,2

Comments

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

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

Equals 2^n - 1 - A095941(n).

Column k=1 of A360634.

Sequence in context: A350104 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