At 06:16 PM 7/13/2004, Edwin Clark wrote:
Thinking of John McCarthy's suggestion, I just submitted the following sequence to the OEIS
1, 3, 6, 11, 18, 28, 42, 61, 86, 119, 162, 217, 287, 375 1, 2, 3, 5, 7, 10, 14, 19, 25, 33, 43, 55, 70, 88 first differences 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18 second differences
The nth term is the number of subsets S of {1,2,...,n} which contain a number that is greater than the sum of the other numbers in S. Actually this is just 2^n-1-b(n) where b(n) is the number of "weakly egalitarian" non-empty subsets of {1,...,n}. But somehow it seems simpler.
Perhaps someone can find a nice formula for the nth term.
The second differences are sequence A000009, partitions into distinct parts. This is easy to see. 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). -- Fred W. Helenius <fredh@ix.netcom.com>