login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 6
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[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).

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 20 06:36 EDT 2019. Contains 322294 sequences. (Running on oeis4.)