Math Question (combinations)

Factual Questions
1

I need a method to determine the total number of possible combinations of a set (I’ll use six names for this example). In this case, the order of the names within each combination doesn’t matter, but I do need to handle the various sized combinations, as a single name is considered a valid combination, as are two, three, four, etc. names.

I’ll use the names:

Bob
Sue
Joe
Wes
Deb
Viv
With that said, the following are all considered valid combinations:

Bob, Sue, Joe
Viv
Deb,Viv,Joe,Wes,Sue,Bob

The last line above is considered the same combination as:
Bob,Sue,Joe,Wes,Deb,Viv
I hope I’ve explained this well enough, and I think I’ve covered all of the bases. Any help would be appreciated, as my head has fried from the various permutation/combination algorithms out there.

2
3

There are 2^n subsets.
One less in your case if you exclude the empty set.

Think of it as a binary string with each bit representing one element. If the element is in your subset, then the bit is one, otherwise it is a zero.

4

You’re looking for the total number of non-empty subsets, regardless of size, chosen from a set of size N. Correct?

In that case, the answer is 2[sup]N[/sup] - 1. To see this, consider the first person. She’s either in a given set, or she’s not. Similarly, the second person is in the set, or he’s not. And so on down the line; you can determine the set by making N choices, one for each person, for which you have two options each way. This would yield 222*…*2, N times, or 2[sup]N[/sup]. However, one of the possible sets you get this way contains nobody at all. So subtract one, for a total of 2[sup]N[/sup] - 1.

5

Ruminator, thanks for the link but I was already googled out trying to find which one of the many combination/permutation methods I needed.

MikeS and unclelem, thanks a million (or approximately 2[sup]20[/sup]- 1), that’s exactly what I needed. :slight_smile: