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

%I

%S 1,3,6,11,18,28,42,61,86,119,162,217,287,375,485,622,791,998,1251,

%T 1558,1929,2376,2912,3552,4314,5218,6287,7548,9031,10770,12805,15180,

%U 17945,21158,24883,29193,34171,39909,46511,54095,62792,72749,84132,97125

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

%C Convolution of A000009 and A001477. - _Vaclav Kotesovec_, Mar 12 2016

%H T. D. Noe and Alois P. Heinz, <a href="/A095944/b095944.txt">Table of n, a(n) for n = 1..10000</a> (first 500 terms from T. D. Noe)

%F 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_.

%F a(n) ~ 3^(3/4) * n^(1/4) * exp(sqrt(n/3)*Pi) / Pi^2. - _Vaclav Kotesovec_, Mar 12 2016

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

%e 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.

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

%t Accumulate[ Accumulate[q = PartitionsQ[ Range[1, 50]]]+1] - Accumulate[q] (* _Jean-Fran├žois Alcover_, Nov 14 2011 *)

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

%K nice,nonn,easy

%O 1,2

%A _W. Edwin Clark_, Jul 13 2004

%E More terms from _John W. Layman_, Aug 10 2004

%E More terms from _Giovanni Resta_, Mar 16 2006

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 May 22 18:53 EDT 2019. Contains 323481 sequences. (Running on oeis4.)