Math problem on combinations of components

General Questions
#1

Let’s say you have a system where elementary components can be combined from 0-1 times with each other. E.g.:
If you only have component A, you have 1 possibility: A.

If you have components A and B, you get: A, B, A+B for a total of 3 possibilities.

A, B, C: A, B, C, AB, AC, BC, ABC = 7 possibilities

A, B, C, D: A, B, C, D, AB, AC, AD, BC, BD, CD, BCD, ACD, ABD, ABC, ABCD = 15 possibilities.

Is there a formula that allows one to calculate how many possibilities exist for each number of components?

#2

If I understand you correctly, what you have is the power set of your original set (i.e. the set of its subsets) excluding the empty set. If the cardinality of the original set is n, then the cardinality of its power set is 2^n. The formula you’re looking for should therefore be 2^n - 1.

#3

Shouldn’t a set of 3 lead to a result of 8 then? Did I miss one possibility for that set?

Would a set of 5 lead to 24 possibilities?
A,B, C, D, E =

A, B, C, D, E (5)
AB, AC, AD, AE, BC, BD, BE, CD, CE, DE (10)
ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, CDE (9)
ABCD, ABCE, ABDE, ACDE, (4)
ABCDE (1)
Maybe I double counted or missed some but that gives me 29.

#4

A set of 3 leads to 2^3 - 1 = 7 possibilities, as in the OP. A set of 5, to 2^5 - 1 = 31 possibilities. You missed BDE and BCDE.

#5

Hypnagogic_Jerk is right

For 3 you have 2^3-1 = 7.

for 5 you have 2^5-1 = 31 possibilities (your list is missing BDE and BCDE).

for 6 you would have 2^6-1 =63 possibilities

The easiest way to see why this is true is that each component can either be in a given entry or not in a given entry and each different combination of in and out will produce a different entry.

For example the entry ABD is represented by

A=in
B=in
C=out
D=in
E=out

There are 2^N different combinations of in and out for N components so this would suggest 2^N different possible entries, however there is one exception is that if you choose “out” for all components then you don’t have an entry. Hence the final result of 2^N-1.

#6

You’re right. Thanks.

#7

Said another way, it’s a binary number, where each component is represented by a single bit. So each bit is either zero (= componenet left out) or one (=component included). So there are 2n possibilities. If you have, say 8 possible components, it’s the same thing as an 8-bit number with 28 = 256 possibilities.

And as everyone has said if you insist that all zeros = no components at all not be counted, the final number is 2n - 1 possibilities. So for 8 components it becomes 28 = 256 - 1 = 255 possibilities.