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

Author

W. Edwin Clark, Jul 13 2004

Keywords

• nice
• nonn
• easy

Comments

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

Examples

			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.
		

Links

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

Crossrefs

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

Column k=1 of A360634.

Programs

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

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<=jN. 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

Extensions

More terms from John W. Layman, Aug 10 2004

More terms from Giovanni Resta, Mar 16 2006