Solving the Subset Problem: Finding the Count of Valid Sets from 1 to N

[SeventhSigma]

If I have a set of numbers from 1 to N, I want to know how to count sets such that the highest number in the set is smaller than the sum of the rest of the subset.

example - (4,7,8) is OK because 4+7>8
(1,2,3,6) is not OK because 1+2+3<=6

Not even sure how to begin @____@

 

[DonAntonio]

If I have a set of numbers from 1 to N, I want to know how to count sets such that the highest number in the set is smaller than the sum of the rest of the subset.

example - (4,7,8) is OK because 4+7>8
(1,2,3,6) is not OK because 1+2+3<=6

Not even sure how to begin @____@

I'm not sure what you meant by "how to count sets such that...". Do you mean you have to characterise these sets, build them...or what?

If you want to build them, take any number of natural numbers a_1, a_2,...,a_n , evaluate their sum S=a_1+...+a_n ,and now

just take ANY number H &gt; S\Longrightarrow \{a_1,...,a_n,H\} is a set as you want.

If you want something else write it down clearly.

DonAntonio

 

[SeventhSigma]

I'm not trying to build sets; I'm trying to count valid subsets.

The main set, call it S, is a list from 1 to N (N can be anything).

I am trying to figure out a good approach/formula for counting valid subsets of S. A valid subset is one where the largest element of the subset is less than the sum of the rest of the subset.

 

[SteveL27]

I'm not trying to build sets; I'm trying to count valid subsets.

The main set, call it S, is a list from 1 to N (N can be anything).

I am trying to figure out a good approach/formula for counting valid subsets of S. A valid subset is one where the largest element of the subset is less than the sum of the rest of the subset.

The way to begin is to start by computing the sets by hand for n = 1, 2, etc. After a while you'll either see a pattern or realize that the combinatorics are too complicated for you to figure out.

The other thing to do as you go through these exercises is to develop some notation and start to gain familiarity with how the sets work.

So let's take n = 1.

We only have two possible subsets, \emptyset and {1}.

\emptyset has no largest element so there's nothing we can say about it. From now on we won't consider the empty set.

The largest element of {1} is 1. Let's denote this as L({1}) = 1. For any set, L(A) is the largest element of the set.

What's the sum of the remaining elements? Well the set of remaining elements other than 1 is empty. The empty sum is zero. Let's denote this as S({1}) = 0. In other words for any set A, S(A) is the sum of the elements in A excluding L(A).

Now there are three possibilities for any set A:

* S(A) < L(A). In this case we'll call A an "L-set," for "less than."

* S(A) = L(A). In this case we'll call A an "E-set," for "equal."

* S(A) > L(A). In this case we'll call A a "G-set," for "greater than." These are the ones you're interested in. My notation is backward from your description, my apologies. This seemed natural to me because if you arrange the elements in order, the largest is on the right and the sum of the rest of them is on the left. So S is to the left of L in my mind. You see that a key part of the process is developing your own mental model of the problem.

With this notation, let's just bang out a bunch of examples and see what we see.

Also note that your problem has a constraint that makes it much easier than it could be. For each n we only have to consider subsets of {1, 2, 3, ...n}. In other words we don't have to deal with arbitrary subsets of the natural numbers such as {47, 100, 148}, which is an L-set. But we aren't considering those types of arbitrary sets. For us, the only possible 3-element set is {1,2,3}, which happens to be an E-set. So your problem is a special case of a much harder problem.

Ok for n = 1 we already saw that we have an enumeration of the subsets:

{1}: L

For n = 2 we have:

{1} : L
{2} : L
{1, 2} : L

We now make a couple of handy observations. Every singleton is an L-set. And every 2-element set is an L-set. Handy to know, saves us some thinking as we go. You see the point of these warmup exercises is to start to become familiar with the problem space.

For n = 3 we have

{1} : L
{2} : L
{3} : L -- remember we don't even have to think about singletons, we know they're L's.
{1,2} : L
{1,3} : L
{2,3} : L -- likewise the 2-elt sets are L's.
{1,2,3} : E -- Ok we finally saw something interesting. Our first E-set.

Also note that your table always has 2ⁿ - 1 entries. That's the number of nonempty sets in the power set of an n-element set.

Now I won't write out the entire table for n = 4. There are 15 nonempty subsets. Four are singletons, six are 2-elt sets ({1,2}; {1,3}; {1,4}; {2,3}; {2,4}; {3,4)}. All of these are L-sets.

When we get to the 3-elt sets we have

{1,2,3} : E
{1,2,4} : L
{1,3,4} : E
{2,3,4} : G -- Hooray, our first G-set, which is the type you are interested in.

And finally the 4-banger.

{1,2,3,4} : G -- Our second G-set.

So if G(n) is the number of G-sets for n, we have G(1) = G(2) = G(3) = 0; and G(4) = 2.

I'll leave the rest to you. Clearly n = 5 is tedious and n = 6 more tedious still. But at some point you might see the pattern by which G-sets are formed.

I hope I provided an answer to the question, How do we start a problem like this?

What we do is start computing the objects of interest by hand for n = 1, 2, ...

As we go, we are forced to confront some conceptual issues such as remembering that an empty sum is zero. We also develop some notation to serve as a shorthand for ideas that we're using over and over. And as we go, we start to develop some skill at manipulating the objects of interest. We know without having to think that singletons and 2-bangers are L-sets. We know that the smallest G-set is {2,3,4}, and so on.

I think that this is going to get combinatorially tricky as the numbers get larger. But this is how to get started. Roll up your sleeves and look at examples.

ps -- If you know a programming language, this is the kind of problem that would be straightforward to program. The benefit of that approach is that you can produce a table for G(n) for much larger values of n than you could do by hand. However there is also some virtue to writing out a lot of cases by hand so you develop intuition for the problem.

 

[dodo]

On the subject of finding shortcuts, it may be useful to realize that, for N>3, the whole set S={1,2,3,...N} is a 'G-set' (thus 'valid'), since the largest element is N and the sum of the others is N(N-1)/2, and (N-1)/2 > 1 when N>3. On these conditions, any subset including N will be 'valid', as the sum of the others will not be higher than in the worst case, S itself.

 

[SeventhSigma]

I've tried most of these techniques already; in all actuality my set S is more like {1, 2, 3, 4, 6, 9, 13, 19, 28, 41} where the first three terms are hardcoded and the rest: a(n) = a(n-1) + a(n-3)

Problem: When I try to even list out all possible sets by hand, I don't see any patterns, nor do I know how to take advantage of combinatorics. Every time I think I've found a pattern, it diverges. I am aware of the points stated so far in this thread though. I think my issue is understanding the combinatorics behind the counting.

 

[DonAntonio]

On the subject of finding shortcuts, it may be useful to realize that, for N>3, the whole set S={1,2,3,...N} is a 'G-set' (thus 'valid'), since the largest element is N and the sum of the others is N(N-1)/2, and (N-1)/2 > 1 when N>3. On these conditions, any subset including N will be 'valid', as the sum of the others will not be higher than in the worst case, S itself.

And that's precisely the reason why it is not true that any subset containing N will be valid!

For example, for N\geq 3 , the set \{1,2,N\} is not valid...

In fact, S is not the "worst case" but the "best"...

DonAntonio

 

[SeventhSigma]

There are many subsets containing N that work, but not all

 

[SeventhSigma]

I might also note that I have written a program that will show all the combinations but it finds them all through brute force. OK for small S, not okay for large S.

 

[SeventhSigma]

Still not finding any pattern... how to use combinatorics here?

 

[dodo]

In fact, S is not the "worst case" but the "best"...

Oh boy, what was I smoking... sorry about that! You are right. Post #5 should be read only up to "... when N>3", the last sentence is wrong wrong wrong.

 

[SeventhSigma]

Is anyone able to help?

 

[Petek]

Here's a general suggestion that may or may not help: You say that you have calculated your desired result for small values of N. Search for that sequence in the On-Line Encyclopedia of Integer Sequences. If you get a match, the information might be useful.

 

[SeventhSigma]

I have had that site open pretty much the entire time I've been working on this and nothing's been particularly helpful, unfortunately. None of the sequences match (or any of the subsequences I get when I try creative ways to partition the results).

 

[dodo]

I wonder (without really knowing what I'm talking about) if the problem can be approached from the other end: counting ways to partition an integer K as a sum of distinct terms, all smaller than your given N; and then adding all these counts from K=N+1 to N(N-1)/2.

 

[SeventhSigma]

perhaps, but for very large N I am not sure if that will work because it would require calculating that for each and every K.

 

[DonAntonio]

perhaps, but for very large N I am not sure if that will work because it would require calculating that for each and every K.

Have you thought of the not-at-all remote possibility that there is no pattern whatsoever for your problem?

Perhaps this is one of those problems that require to know the exact set to work with in order to construct all the valid subsets...

DonAntonio

 

[dodo]

perhaps, but for very large N I am not sure if that will work because it would require calculating that for each and every K.

Plus, having a theoretical answer or a practical method are two very different things; your comment suggests that you are looking for the latter, but the former is a necessary step anyway.

P.S.: Please compare the output of the following Python program (Python is almost pseudo-code, so it should be "understandable"), to see if this is what you expect. (I need some time to explain to myself why this seems to work; my subconscious tends to work faster --though not always right-- than my rational part, I guess.)

At first I thought this program would run in linear time because, while the problem is subdivided in two and recursively solved, I thought the left branch of the tree would extinguish pretty quickly. When trying with larger numbers I see that this is not really true. It's still way faster than the brute-force approach of generating all subsets and counting them.

Output:

1 0
2 0
3 0
4 2
5 7
6 19
7 46
8 104
9 224
10 470
11 970
12 1979
13 4009
14 8083
15 16248
16 32600
17 65330
18 130820
19 261838
20 523918

Program:

#!/usr/bin/python

def main():
	for n in range(1, 21):
		print n, count(n)

def count(n):
	return compare(n, n - 1)

def compare(n, p):
	if n <= 0:
		return 2**p - 1
	if p <= 0:
		return 0

	return compare(n - p, p - 1) + (p > n) + compare(n, p - 1)

main()

 

[dodo]

Here is some rationale as to why the above program appears to work. Consider, for example, the case N=5, where you want all subsets of {1,2,3,4} whose sum is larger than 5. I have listed all subsets below.

                 Sum
 1    {      1}   1
 2    {    2  }   2
 3    {    2 1}   3
 4    {  3    }   3
 5    {  3   1}   4
 6    {  3 2  }   5
 7    {  3 2 1}   6
--------------------
 8    {4      }   4
--------------------
 9    {4     1}   5
10    {4   2  }   6
11    {4   2 1}   7
12    {4 3    }   7
13    {4 3   1}   8
14    {4 3 2  }   9
15    (4 3 2 1}  10

The middle row (#8) contains a subset with only one element, N-1 = 4.

And notice that, by construction, all sums *after* the middle row are equal to 4 plus the corresponding sums *before* the middle row.

Therefore, the sums larger than 5 are:
- the sums after the middle (rows 9-15) larger than 5, which are as many as the sums before the middle (rows 1-7) that are larger than 5-4 = 1;
- plus 1 if the middle row were larger than 5, which it isn't; so nothing added here;
- plus the sums before the middle (rows 1-7) which are larger than 5.

So we are referring now *only* to the sums in the first rows (1-7).

These sums before the middle can be figured out recursively, as they follow the same pattern:

               Sum
 1    {    1}   1
 2    {  2  }   2
 3    {  2 1}   3
-----------------
 4    {3    }   3
------------------
 5    {3   1}   4
 6    {3 2  }   5
 7    {3 2 1}   6

where the three sums after this new middle (rows 5-7) add to 3 plus the corresponding sums in rows 1-3.

The final line in the 'compare' function

return compare(n - p, p - 1) + (p > n) + compare(n, p - 1)

is the one responsible for subdividing the problem in the three parts I mentioned before (after the middle, middle, and before the middle). The variable 'p' is meant to represent a power of 2.

 

[SeventhSigma]

However those results aren't quite right... should be 2, 7, 19, 47, 108, 236, 501, onward

 

[dodo]

However those results aren't quite right... should be 2, 7, 19, 47, 108, 236, 501, onward

Hmm, curious... I tried generating the subsets by brute force and I get the same numbers as I listed above, not yours. Let me re-check.

 

[SeventhSigma]

some raw output: http://justpaste.it/yc5

 

[dodo]

Ahhh... I was always using {1,2,3,...,N} (with all integers from 1 to N) as my primary set of length N. If you choose an arbitrary set of length N, then the count for N will obviously depend on the particular set, not just on N or on the largest integer in the set.

Edit: Oh, wait, you said in post #6 that the list comes from a specific recurrence sequence. Also, I see now that I have the comparison criterion wrong: a subset is valid if the largest element in the subset (not N, nor the largest in the original set) is smaller than the sum of the others; this renders my subdivision strategy useless.

 

[SeventhSigma]

right, the subset,sorry for the confusion

 

[dodo]

Hmm, not all is lost. Here is a variation of the program; it produces the output below in under a second, but it will get terribly slower for larger N, it is not linear.

Output:

4 2
5 7
6 19
7 47
8 108
9 236
10 501
11 1045
12 2149
13 4378
14 8869
15 17892
16 35988
17 72254
18 144886
19 290271
20 581207

Program:

#!/usr/bin/python

def main():
	sequence = [1,2,3]

	for n in range(4, 21):
		addOneMore(sequence)
		print n, count(sequence, n)

def addOneMore(sequence):
	sequence.append(sequence[-1] + sequence[-3])
	
def count(sequence, n):
	sum = 0
	for largest in range(3, n):
		sum += compare(sequence, sequence[largest], largest)
	return sum

def compare(sequence, top, p):
	if top <= 0:
		return 2**p - 1
	if p <= 0:
		return 0

	return compare(sequence, top - sequence[p - 1], p - 1)	\
	       + (sequence[p - 1] > top)			\
	       + compare(sequence, top, p - 1)

main()

Perhaps the only Python-specifics needed to understand this are that sequence indexes are 0-based (from 0 to length-1), and that negative indexes pick items from the end: sequence[-1] is the last, sequence[-2] the next to last, and so on. The iterator range(a,b) will iterate starting from 'a' and until less than 'b'; that is, up to b-1.

 

[SeventhSigma]

sum-k's fall into an arithmetic progression across N's... but it's not clear how to derive them otherwise

 

[dodo]

sum-k's fall into an arithmetic progression across N's... but it's not clear how to derive them otherwise

Sorry, I don't know which sum do you mean.

 

[SeventhSigma]

say N=5 or [1, 2, 3, 4, 6]

and we count invalid solutions instead:
there are X ways to have an inner sum of k:

there are 4 ways to have an inner sum of 1
(1, 2) (1, 3) (1, 4) (1, 6)
there are 3 ways to have an inner sum of 2
(2, 3) (2, 4) (2, 6)
there are 5 ways to have an inner sum of 3
(1, 2, 3) (1, 2, 4) (1, 2, 6) (3, 4) (3, 6)
there are 3 ways to have an inner sum of 4
(1, 3, 4) (1, 3, 6) (4, 6)
and so forth

 

[SeventhSigma]

lots of patterns but they all seem random

 

[SeventhSigma]

Does anyone have any further thoughts on this problem?

 

[haruspex]

This is connected with partition numbers, in particular, restricted partitions: http://en.wikipedia.org/wiki/Partition_(number_theory)#Restricted_partitions.
Let PD(n) be the number of partitions of n into distinct positive integers.
An 'invalid' set in the OP is one in which the largest in the set, Y, exceeds or equals the sum, X, of the rest. For a given X and any N >= Y >= X, there are PD(X) of these. (Except, when Y=X we have to exclude the partition of X as just X, otherwise the invalid set would consist of the same number twice.) So in total there are N.PD(1) - 1 + (N-1).PD(2) - 1 + ... + 1.PD(N) - 1 that are subsets of {1..N}.
Check: N = 5:
5.PD(1) + 4.PD(2) + 3.PD(3) + 2.PD(4) + 1.PD(5) - 5 =
5.1 + 4.1 + 3.2 + 2.2 + 1.3 - 5 = 17
But these are only the invalid sets of 2 or more numbers. Any single member set is necessarily invalid, for a total of 22.
The number of valid sets = 31 - 22 = 9, which I believe is correct.

 

[ClifDavis]

I've tried most of these techniques already; in all actuality my set S is more like {1, 2, 3, 4, 6, 9, 13, 19, 28, 41} where the first three terms are hardcoded and the rest: a(n) = a(n-1) + a(n-3)

Problem: When I try to even list out all possible sets by hand, I don't see any patterns, nor do I know how to take advantage of combinatorics. Every time I think I've found a pattern, it diverges. I am aware of the points stated so far in this thread though. I think my issue is understanding the combinatorics behind the counting.

This is a very different and much more tractable problem. It is easier than finding the solutions for sets, S'={1,2,3,4,5,6,7,...,n} because S={a(1),a(2),a(3),...,a(n)} has much more structure.

For starts try to find a formula that will tell you exactly how many subsets of S have totals that are exactly equal to a(n). For any of these subsets, if you add an extra a(i) to it, it will form the basis for one of the subsets you're counting. So for each of these subsets check how many ways you can add to them without creating duplicates.


The case of S'=(1,2,3,...,n) is interesting though.

 

[SeventhSigma]

Can you provide an example ? Not sure I understand

 

[ClifDavis]

Let's take the general case of count(n) so that S={a(1),a(2),a(3),...a(n-3),a(n-2),a(n-1),a(n)}

Now we know the a(i) are positive and increasing, and you should be able to prove it if needed.

We also know that a(n)=a(n-1)+a(n-3). But they are increasing so a(n-2)>a(n-3). So it follows that after we add a(n-1) to both we get a(n-1)+a(n-2)>a(n-1)+a(n-3)=a(n). In other words any subset of S that contains both a(n-1) and a(n-2) is one we should count. The other smaller elements can either be present or not present (two possibilities) and there are exactly n-3 of these other elements so there are 2^(n-3) different subsets that go into our count so far (where 2^(n-3) should be read as 2 to the power of (n-3)).

Of course that isn't all by a long shot. So far we just have the subsets counted that contain both a(n-1) and a(n-2). Let's stick with a(n-1) and drop a(n-2). Now as we started out noticing a(n)=a(n-1)+a(n-3). So if we take any subset that contains a(n-1) and a(n-3) and at least one more element then we have a subset of S we should count. If the subset contained a(n-2) we would have already counted it in our previous steps, so there are only n-4 other elements that might be present or not. The only possibility we don't want to count is where they all aren't present and just leave us with {a(n-3),a(n-1)} which isn't quite enough and so we have (2^(n-4))-1 additional subsets to count.

So far we have count(n)=(2^(n-3))+(2^(n-4))-1+?

Have we counted everything that contains a(n-1)? We've counted everything that contains a(n-1) and either a(n-2) or a(n-3) or both. Are there other combinations that add up greater than a(n-3) (so that when combined with a(n-1) will be greater than a(n))? Why yes there are. You should be able to see there are count(n-3) of them because of the way count is defined.

So we now have count(n)=(2^(n-3))+(2^(n-4))-1+count(n-3)+?
with just having counted the Subsets containing a(n-1).


Can you take it from there?

 

[SeventhSigma]

not so much. I am trying to use a smaller set of S to see if I can count them properly. I am not sure that approach works because it's easier to count the extremities than it is to count the nitty gritty stuff towards the center of S where stuff gets messier

 

[haruspex]

I'm puzzled there's been no response to my post (#31).
Isn't it the answer to the originally posed question? Do I need to explain more?

 

[ClifDavis]

I'm puzzled there's been no response to my post (#31).
Isn't it the answer to the originally posed question? Do I need to explain more?

As you note, you are answering the original question for {1,2,3,...,n} whereas what he actually needs is an answer to the simpler question for {a(1),a(2),a(3),...a(n)} which generally looks like {1,2,3,4,6,9,13,...}.

More importantly your answer is wrong for the question you are answering.

For N=5 you calculate an answer of 9 subsets. But the subsets that fit the criteria are:
{1,2,3,4} 1+2+3+4=13>5
{2,3,4} 2+3+4=9>5
{1,3,4} 1+3+4=8>5
{3,4} 3+4=7>5
{1,2,4} 1+2+4=7>5
{2,4} 2+4=6>5
{1,2,3} 1+2+3=6>5

By my count that makes 7. If you could cough up another two, that would be interesting.

So yes, I think you do need to explain more.

 

[ClifDavis]

not so much. I am trying to use a smaller set of S to see if I can count them properly. I am not sure that approach works because it's easier to count the extremities than it is to count the nitty gritty stuff towards the center of S where stuff gets messier

Well the reason that I initially suggested that you start by checking the number of subsets of S that total to n is that those subsets are the key to counting the qualifying subsets that total to more than n. And finding them points out that you only have to count the extremities in that you only have to count subsets that contain a(n-1) which we've already done, or that don't contain a(n-1) and do contain a(n-2).

At some point you do have to look at the simple sets that don't have enough elements to fit the general case, but until you look at the general case, you don't know how many of the simple cases to look at.

Our basic relationship a(n-3)+a(n-1)=a(n) was the key to counting the number of qualifying subsets that contained a(n-1). To look at those that don't contain a(n-1) we want to get rid of the a(n-1) in our equivalence expression, so we use the known fact from our definition of the a function that a(n-1)=a(n-2)+a(n-4). So we have a(n)=a(n-3)+a(n-1)=a(n-3)+a(n-2)+a(n-4) or to rearrange the terms slightly, we have a(n-4)+a(n-3)+a(n-2)=a(n) and so we have another equivalence where a(n-1) does not occur. This one will be our starting point for counting qualifying subsets where a(n-2) is in the subset.

Now counting the qualifying subsets with a(n-2) as the largest element is something we still have to do. But once we are through we will want to move on to get the next equivalence that doesn't contain a(n-2) either. We know that a(n-2)=a(n-3)+a(n-5) so we can use that to get rid of a(n-2).
So, we have
a(n)=a(n-4)+a(n-3)+a(n-2) and applying the definition of a to a(n-2)
=a(n-4)+a(n-3)+a(n-3)+a(n-5)
=a(n-5)+a(n-4)+a(n-3)+a(n-3) which is okay except we have two a(n-3) but as before
=a(n-5)+a(n-4)+a(n-3)+a(n-4)+a(n-6) we get rid of an a(n-3)
=a(n-6)+a(n-5)+a(n-4)+a(n-4)+a(n-3) but now we have two a(n-4)s so get rid of 1
=a(n-7)+a(n-6)+a(n-5)+a(n-5)+a(n-4)+a(n-3) and now two a(n-5)s...
=a(n-8)+a(n-7)+a(n-6)+a(n-6)+a(n-5)+a(n-4)+a(n-3)

and you see what is happening. Every time we use the definition of the function a to get rid of a duplicate, it creates a new duplicate and it will continue to do so until we extend down to an a(1) term at which point we'll have a duplicate a(3) term. In other words the sum
a(1)+a(2)+a(3)+...+a(n-3)<a(n). If we're doing this right, we should prove that by induction on n. And since the sum of a(1) to a(n-3) is less than n, any qualifying subset must contain a(n-2) or a(n-3) or both. So our sets with extreme values really are all we have to count.

Now there's a still a trick to counting qualifying subsets that have a(n-2) as their largest element, but if you start off counting the sets with a(n-2) as the largest element the same way I did for sets with a(n-1) as the largest element, you will run into it and hopefully see the solution.

 

[haruspex]

For N=5 you calculate an answer of 9 subsets. But the subsets that fit the criteria are:
{1,2,3,4} 1+2+3+4=13>5
{2,3,4} 2+3+4=9>5
{1,3,4} 1+3+4=8>5
{3,4} 3+4=7>5
{1,2,4} 1+2+4=7>5
{2,4} 2+4=6>5
{1,2,3} 1+2+3=6>5

By my count that makes 7. If you could cough up another two, that would be interesting.

The original statement is this:

If I have a set of numbers from 1 to N, I want to know how to count sets such that the highest number in the set is smaller than the sum of the rest of the subset.

Note: highest number in the subset (not necessarily N).
This was made clearer in post #3:

A valid subset is one where the largest element of the subset is less than the sum of the rest of the subset.

Necessarily, no subset of 1 or 2 elements can be valid.
The following are the 9 valid for N=5:
2, 3, 4; 2, 4, 5; 3, 4, 5; 1, 2, 3, 4; 1, 2, 3, 5; 1, 2, 4, 5; 1, 3, 4, 5; 2, 3, 4, 5; 1, 2, 3, 4, 5;

There is an easy connection between the two interpretations. If OP(N) is the answer to the original problem and OPN(N) is the answer when the highest term in each subset is required to be N then
OP(N+1) = OP(N) + OPN(N+1)
E.g. OP(4) = 2.

Presumably the same misunderstanding has arisen regarding the a(n) version of the problem; luckily the corresponding relationship applies: AP(N+1) = AP(N) + APN(N+1) where N is the number of elements in the full set.

I agree this version of the problem looks far more amenable.

 

[SeventhSigma]

ClifDavis I think we may be talking about different problems. There are possible valid subsets where values aren't from extremities at all, or they may be from all over the place, and so on. You can't just count from extremity cases.

Look at the solution for N=10:

http://pastebin.com/jr6cr7q1

I don't think the approach you are describing emulates the nature of this output. It's looking at a subset and checking the sum of inner elements against the highest element of that subset.

N=10 means S goes up to a(10), or S = [1, 2, 3, 4, 6, 9, 13, 19, 28, 41]
one valid subset might be (1, 6, 13, 19) because 1+6+13 = 20, which is larger than 19.
haruspex: Those solutions aren't right either because your subsets include numbers (namely 5 in this case) that aren't in S.

 

[haruspex]

ClifDavis I think we may be talking about different problems. ... It's looking at a subset and checking the sum of inner elements against the highest element of that subset.

As I said, I believe ClifDavis' interpretation ("APN(N)", where a(N) is the highest in the set) is readily mapped to what you intended ("AP(N)") according to: AP(N+1) = AP(N) + APN(N+1). I.e. AP(N) = sum APN(1) to APN(N).

haruspex: Those solutions aren't right either because your subsets include numbers (namely 5 in this case) that aren't in S.

Quite so - at #31 I was answering the problem as originally posted. I came into the thread just at the point where you added the explanation about a(n) and posted my input without reading that update.

 

[SeventhSigma]

I don't think so, because in his earlier analysis he compares subset sums to 5, which is not a valid comparison. You need to compare the highest number of the subset against the sum of the rest of the subset

 

[haruspex]

I don't think so, because in his earlier analysis he compares subset sums to 5, which is not a valid comparison. You need to compare the highest number of the subset against the sum of the rest of the subset

Sorry, you've lost me. Which post is that in? If you mean post #37, that's where ClifD was saying I had the wrong answer to your original question (1, 2... n, rather than a(1), ... a(n)).

 

[ClifDavis]

I don't think so, because in his earlier analysis he compares subset sums to 5, which is not a valid comparison. You need to compare the highest number of the subset against the sum of the rest of the subset

haruspex is quite right. I had gotten the statement of the problem confused from looking at other people's posts and programs rather than yours. Essentially I was showing how to count the new elements for n and not all the elements for n. And I wasn't putting the last term in the subset. Which doesn't effect the count. However it means that my explanation of what I was doing is totally confusing.

To rephrase what he was saying into the notation I was using, if count(n) gives the count for all the qualifying subsets of {a(1),...a(n)} and countnew(n) gives the count of just those qualifying subsets that contain a(n), then count(n)=countnew(n)+count(n-1)

Or conversely countnew(n)=count(n)-count(n-1) which is something that is handy to know.

But what it means is if you have an equation for countnew(n)=stuff then you also have a valid recurrence relationship count(n)=count(n-1)+stuff.

But now that we're on the same page, I'll go back and cover what I was doing for the general case and use smaller arguments for illustration which may make it easier to follow. But not tonight. Time will be tight Sunday and Monday, so it may be Tuesday before I can run through a reasonable explanation, though I'll try to slip it in earlier. If you solve it in the meantime or if haruspex can give you useful clues then it won't matter.

But the important points are still the same. Your a(n)'s are positive and increasing. a(1)+a(2)+a(3)+...a(n-3)<a(n) so any subset to be counted that contains a(n) as the largest element must contain a(n-1) or a(n-2) or both. And if you look at the different subsets containing a(n) as the largest element where the other elements add up to a(n), this will guide you to the different categories of subsets that you can count without having to explicitly create them.

 

[haruspex]

Fwiw, I had a go at this simpler problem:
Sn = {A(1), .. , A(n)}, where the A(n) satisfy the recurrence relation A(n) = A(n-1) + A(n-3), etc.
How many subsets of Sn sum to A(n) exactly?
I can't even solve that yet. The problem is that some such subsets cannot be obtained by repeated application of the recurrence relation to break down the target sum. E.g. A(1)+A(2) = A(3). So instead I'll just go for the lower bound which only counts the subsets that can be obtained in this way.

Let T(n,P) = number of subsets that add up to the same as the terms indicated by the bit pattern P, e.g.
P = 1 stands for just the term A(n)
P = 11 stands for A(n-1)+A(n)
P = 101 stands for A(n-2)+A(n)
etc.
T(n,1) = 1 + T(n-1,101)
T(n,101) = T(n-1,111) + T(n-2,1)
T(n,1111) = T(n-1,111) = T(n-2,11)
T(n,11) = T(n-1,1) + T(n-1,1111)
whence
T(n,1) = 1 + T(n-2,111) + T(n-3,1)
T(n,111) = T(n-2,1) + T(n-3,111)
For the general solution we drop the "1+" and try λ^{n}.
This yields the polynomial equation:
λ^{3} +/- λ - 1 = 0
Bringing the "1+" back in, the particular solution to be added on is T(n,1) = 0, T(n,111) = -1.
The general solution is therefore
\Sigma^{6}_{i=1} k_{i}λ_{i}^n
where the λ_{i} are the roots of the polynomial.

 

[haruspex]

OK, here's my attempt at the actual problem. Methods and results largely the same.

Let C(n) be the number of subsets of Sn that sum to more than A(n).
Let D(n) be the number of subsets of Sn that sum to more than A(n)+A(n-1).

Starting with a summation target of A(n)+1 (or higher):
1. Suppose we use A(n). We now only have to use one other, i.e. any of 2^(n-1)-1 subsets. OTOH,
2. if we don't use A(n) we know we must use either A(n-1) or A(n-2) or both.
2a. If we use both then we can use any combination of A(1) to A(n-3), 2^(n-3) subsets.
2b. If we use A(n-1) but not A(n-2) then we have a remaining target of A(n)+1-A(n-1) = A(n-3)+1, for which there are C(n-3) possibilities.
2c. If we use neither A(n) nor A(n-1) then we have a target of A(n)+1 = A(n-2)+A(n-3)+A(n-4)+1. We must use A(n-2). That leaves a target of A(n-3)+A(n-4)+1, for which there are D(n-3) possibilities.
Putting this together:
C(n) = 2^(n-1)-1 + 2^(n-3) + C(n-3) + D(n-3)

Similarly, with D(n), we can use A(n), leaving a target of A(n-1)+1; or not use A(n), leaving a target of A(n)+1 = A(n-2) + A(n-3) + A(n-4) + 1.
D(n) = C(n-1) + D(n-3)

The homogeneous solution is λ^{n}, where λ satisfies the same equation as in the previous post: λ^{3} +/- λ - 1 = 0.
The particular solution is now:
C(n) = (2^n)*7/9; D(n) = (2^n)*4/9 + 1.

 

[SeventhSigma]

I don't think that's right... doesn't return 501 for N=10 although the logic seems to be headed in the right direction

 

[SeventhSigma]

Again I think I maybe haven't made it clear what this problem entails:

If we have N=5 that means S has the first five terms a(1) through a(5): [1, 2, 3, 4, 6]
The answer here is 7 because
(2,3,4) because the internal sum of 5 is greater than 4
(3,4,6) because the internal sum of 7 is greater than 6
(1,2,3,4) because the internal sum of 6 is greater than 4
(1,2,4,6) because the internal sum of 7 is greater than 6
(1,3,4,6) because the internal sum of 8 is greater than 6
(2,3,4,6) because the internal sum of 9 is greater than 6
(1,2,3,4,6) because the internal sum of 10 is greater than 6

A valid subset of S is one where the highest element of that subset is less than the sum of the rest of that subset.

"Starting with a summation target of A(n)+1 (or higher):
1. Suppose we use A(n). We now only have to use one other, i.e. any of 2^(n-1)-1 subsets. OTOH, "

Implies the first summation target we look at for N=5 is A(5)+1 = 6+1 = 7
Now suppose we use A(5) or 6 in our subset: (6)
You say that including anything from the rest of S, (1,2,3,4), is valid here, but it isn't. I could use one other (1,2) giving me (1,2,6) which is not valid because 1+2 is < 6. It is true that 1+2+6 >= 7, but that isn't what we're trying to solve for here.

 

[haruspex]

SeventhSigma, Sorry, I forgot to point out that this is not quite the problem as you stated it, but that it should be mappable to it fairly easily.
First, if you exclude the use in the sum of the top term in the set, that just subtracts 2^(n-1)-1 possibilities. That gets us to the version ClifDavis considered. (I probably could have got straight to that by modifying the argument a little. You might care to try that.) Now you have to sum the counts for n = 1 to N to get the solution to the correct version.

 

[SeventhSigma]

I tried to do that but was getting erroneous values. Would you be able to show how it works for something like N=10 in terms of setup? (I know the answer is 501 there)

N=1, 2, 3: Answer 0
N=4: Answer 2
N=5: Answer 7
N=6: Answer 19
N=7: Answer 47
N=8: Answer 108
N=9: Answer 236
N=10: Answer 501