Thread: Number of possible combinations using different numbers of elements

I looked around and couldn't find anything that fits this question so I'm posting it here.

This is difficult for me because I am not good at math. I'm sure you hear that often in newbies' posts, but I'm seriously bad. I can get basic arithmetic wrong with an abaccus. If math were a video game I would die on the title screen. If math is poetry I'm a Vogon. You get the idea.

So it has taken a LOT of work for me even to get to the point where I can explain it as well as I am about to, and I don't even know if I'm using the right terminology here besidse. But I'm trying to figure out a formula (logorithm? algorithm?) for determining the number of possible combinations for an "object" with 20 different "elements". Note, this is not a question about permutations because it is possible for any number of the elements to be present, and they will always be in the same order. So for each number of elements present there will be a certain number of possible combinations.

If the elements were to be represented by the letters A through T:

The first possible combination has zero elements present, so only one possible combination with that number.

The second has one element present, with 20 possible results; one for each element. A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T.

The third has two elements present, and here's where it starts to get tricky for me. Possible combinations look like this:
AB, AC, AD, AE, AF, AG, et cetera through AT.
BC, BD, BE, BF, BG, BH through BT.
So the first set, the one including A, has 19 combinations. The second has 18. Then I presume, the third (excluding A and B) would have 17, the fourth (excluding A, B, and C) would have 16, down to the last possible combination with two elements, excluding all the elements besides S and T.

Then we get to three element combinations:
ABC, ABD, ABE... 18 combinations
ACD, ACE, ACF... 17 combinations
ADE, ADF, ADG... 16 combinations

and the number of combinations restarts minus one once A has been excluded:
BCD, BCE, BCF... 17 combinations
BDE, BDF, BDG... 16 combinations
BEF, BEG, BEH... 18 combinations

Down to RST, which of course has only one combination.

Now, I could do this the long way and just count all the different combinations, but obviously that would be a lot of work. I know there must be a kind of shortcut, but I can't figure it out. For one thing I couldn't express it even if I could grasp it, but the real problem is that the system I have outlined to this point STOPS WORKING sometime before the end. Because obviously there is only ONE possible combination for all 20 elements: ABCDEFGHIJKLMNOPQRST.

So what am I missing here? Is there a point at which the process reverses itself? Because I can't think through enough steps to find that point. (I'm also bad at chess, for that reason.)

So what is the "shortcut", if there is one? And what would be the proper or formal way to express it?

Originally Posted by macfall

But I'm trying to figure out a formula (logorithm? algorithm?) for determining the number of possible combinations for an "object" with 20 different "elements". Note, this is not a question about permutations because it is possible for any number of the elements to be present, and they will always be in the same order. So for each number of elements present there will be a certain number of possible combinations.
If the elements were to be represented by the letters A through T:

So what am I missing here? Is there a point at which the process reverses itself? Because I can't think through enough steps to find that point. (I'm also bad at chess, for that reason.)

So what is the "shortcut", if there is one? And what would be the proper or formal way to express it?

It is not easy to follow you. As read it, you can use anywhere from zero to twenty of those components. But use each component at most once.

It that is correct the the answer is easy: .
That is just the number of subsets of a set of twenty.