# Math Question (combinations) **URL:** \ **Category:** Factual Questions\ **Created:** [December 17, 2008, 5:39pm UTC](https://boards.straightdope.com/t/math-question-combinations/477598 "2008-12-17T17:39:41Z")\ **Posts on this page:** 5\ **Page:** 1
**Author:** ![DMC](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dmc/32/18049_2.png) [@DMC](https://boards.straightdope.com/u/DMC)\ **Post date:** [December 17, 2008, 5:39pm UTC](https://boards.straightdope.com/t/math-question-combinations/477598/1 "2008-12-17T17:39:41Z")
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. ---
**Author:** ![Ruminator](https://avatars.discourse-cdn.com/v4/letter/r/b9bd4f/32.png) [@Ruminator](https://boards.straightdope.com/u/Ruminator)\ **Post date:** [December 17, 2008, 5:46pm UTC](https://boards.straightdope.com/t/math-question-combinations/477598/2 "2008-12-17T17:46:15Z")
> [@DMC](#): > > I need a method to determine the total number of possible combinations of a set > **[Combination](https://en.wikipedia.org/wiki/Combinations)** > > In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. So, two combinations are identical if and onl... ---
**Author:** ![unclelem](https://avatars.discourse-cdn.com/v4/letter/u/ac91a4/32.png) [@unclelem](https://boards.straightdope.com/u/unclelem)\ **Post date:** [December 17, 2008, 5:48pm UTC](https://boards.straightdope.com/t/math-question-combinations/477598/3 "2008-12-17T17:48:17Z")
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. ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [December 17, 2008, 5:52pm UTC](https://boards.straightdope.com/t/math-question-combinations/477598/4 "2008-12-17T17:52:35Z")
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 2_2_2\*…\*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. ---
**Author:** ![DMC](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dmc/32/18049_2.png) [@DMC](https://boards.straightdope.com/u/DMC)\ **Post date:** [December 17, 2008, 7:37pm UTC](https://boards.straightdope.com/t/math-question-combinations/477598/5 "2008-12-17T19:37:43Z")
**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. 🙂