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

[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

 

[haruspex]

So you found all the roots and coefficients? I haven't tried to do that. Could you post them? Or did you just run through the logic recurrence to see if it gave the right answer?

 

[SeventhSigma]

No I mean I tried to take the general logic of your explanation and see if I could remap it by changing the way I handle targets and inclusions

[1, 2, 3, 4, 6] = S for N=5
so if summation target = 6 that means we would have (4, 6) but the rest of the subset S only works if we take at least 2 elements because (1, 4, 6) would not work, and so on.

Otherwise yes I just went through the recurrence to see if it returned the right answer (wrote a program)

 

[haruspex]

I put my recurrence relation, plus the mapping to your problem, into a spreadsheet and it gave 501 for N=10. You have to be careful where you start the recurrence. C(3) = D(4) = 3, D(3) = 1. If you start too soon you pick up the fictitious value A(0) = 1.
(This is a bit confusing because C(n) is in spreadsheet col D, D(n) in col E.)
n A 2^ C D APN AP
1 1 1 0 0 0
2 2 2 1 0 0 0
3 3 4 3 1 0 0
4 4 8 9 3 2 2
5 6 16 20 9 5 7
6 9 32 43 21 12 19
7 13 64 91 46 28 47
8 19 128 188 100 61 108
9 28 256 383 209 128 236
10 41 512 776 429 265 501
The formulae, starting with N=5, look like:
D5 =C5-1+C3+D2+E2 (i.e. C(n), col D)
E5 =D4+E2
F5 =D5-C5+1
G5 =G4+F5

 

[haruspex]

As I said, the double use of A, C, D for variables and spreadsheet columns is confusing.
In the spreadsheet:
col A is N
col B is A(N)
col C is 2^(N-1)
col D is my C(N)
col E is my D(N)
col F is what I've previously referred to as APN(N)
col G should be the number you're after

The formulae at the end of my previous post refer to spreadsheet columns.
The array starts (N=1) in row 2 of the spreadsheet, row 1 being headings.
I've given the formulae that go in row 5. Above row 5 these don't apply in all columns so you need to plug in the hard numbers.

APN(N) is ClifDavis (mis)reading of the problem, i.e. it takes the target to beat as being A(N), rather than the highest number in the subset. I've kept that in because it is a useful step along the way to the numbers you want.

 

[SeventhSigma]

I am trying to find another way to simplify everything so I can solve this for large n mod m eventually

using your notation:

c(n) = 2^(n-1) - 1 + 2^(n-3) + c(n-3) + d(n-3)
c(1) = 0, c(2) = 1, c(3) = 3

d(n) = c(n-1) + d(n-3)
d(1) = 0, d(2) = 0, d(3) = 1

g(n) = c(n) - 2^(n-1) + 1 + g(n-1)
g(1) = 0

where g(n) is the answer function

but I can rewrite g(n) as
g(n) = n - 2^n + 1 + X
Where X is c(2) + ... + c(n)

What might be a good way to quickly find sums of c(n) sequences? I tried listing everything out longhand:

c(1) = 0
c(2) = 1
c(3) = 3
c(4) = 2^(3) - 1 + 2^(1)
c(5) = 2^(4) - 1 + 2^(2) + 1
c(6) = 2^(5) - 1 + 2^(3) + 3 + 1
c(7) = 2^(6) - 1 + 2^(4) + 2^(3) - 1 + 2^(1) + 3
c(8) = 2^(7) - 1 + 2^(5) + 2^(4) - 1 + 2^(2) + 1 + 2^(3) - 1 + 2^(1)
c(9) = 2^(8) - 1 + 2^(6) + 2^(5) - 1 + 2^(3) + 3 + 1 + 2^(4) - 1 + 2^(2) + 1 + 1
c(10) = 2^(9) - 1 + 2^(7) + 2^(6) - 1 + 2^(4) + 2^(3) - 1 + 2^(1) + 3 + 2^(5) - 1 + 2^(3) + 3 + 1 + 3

d(1) = 0
d(2) = 0
d(3) = 1
d(4) = 3 
d(5) = 2^(3) - 1 + 2^(1)
d(6) = 2^(4) - 1 + 2^(2) + 1 + 1
d(7) = 2^(5) - 1 + 2^(3) + 3 + 1 + 3

so g(10) here would be g(10) = 10 - 2^10 + 1 + c(2) + c(3) + c(4) + c(5) + c(6) + c(7) + c(8) + c(9) + c(10) = 501

 

[haruspex]

Recall that I arrived at:
C(n) = (2^n)*7/9 + \sum^{6}_{i=1}k_{i}λ^{n}_{i} = (2^(n-1))*14/9 + \sum^{6}_{i=1}k_{i}λ^{n}_{i}
where the λ^{i} are the roots of λ^3 +/- λ - 1 = 0
So G(n) = \sum{(2^(n-1))*5/9 + 1 + \sum^{6}_{i=1}k_{i}λ^{n}_{i}}
= ((2^n)-1))*5/9 + n + \sum^{6}_{i=1}g_{i}λ^{n}_{i} + some constant
where the g_{i} are related to the k_{i} by g_{i} = k_{i}*λ_{i}/(λ_{i}-1)

It remains to figure out the λ_{i} (two sets of roots will be complex pairs) and use the first so many values of G(N) to find the g_{i}. The constant should be
-\sum^{6}_{i=1}g_{i}/λ_{i}
Of course, the g_{i} will be such that all the imaginary terms cancel.

 

[SeventhSigma]

I don't really understand that method at all... there's no other shortcut?

 

[Mandlebra]

Some times a generating function approach*is*the short cut

 

[SeventhSigma]

I guess I am just not understanding how generating functions work here because I am trying to solve this for a very large n with modulus, and I worry that using roots will result at in decimal values that will lack precision (assuming that I even figure out how that approach works)

 

[haruspex]

It's not a generating function. Generating functions have the values of interest as coefficients in an infinite power series. It is a closed form expression which, once the constants have been figured out, will produce the answer for any n in a fixed number of steps. You can do the same for all sorts of series. E.g. http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression.
Although the computation involves irrationals, the answer, if calculated precisely, always produces an integer. So you only have to calculate it precisely enough to get the error less than 0.5. The snag is that how accurately the constants need to be calculated probably depends on n.
When I get time I'll have a go at finding the constants.