|
| |
|
|
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.
|
|
18
|
|
|
|
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
|
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
KEYWORD
|
nice,nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
