[Math] Find all unique combinations for all possible group sizes

combinationscombinatorics

I know that if I want to find out the number of combinations for set then I can use this formula as long as I have a fixed number of values being compared at a time (I have to have a set r value).

$$n!\over k!\,(n-k)!$$

I'm looking to find out what the formula would if I wanted to know the sum of all values for r between 1 and n.

For example if my data set is just:

  • Red
  • Green
  • Blue

Then I can have 7 unique groupings if I want to look at all possible group sizes (excluding an empty group):

  • Red
  • Green
  • Blue
  • Red, Green
  • Red, Blue
  • Green, Blue
  • Red, Green, Blue

Best Answer

If you allow the empty set, each of Red, Blue, and Green can be in the group (subset) or not, so there are $2^3=8$ subsets. You made three binary choices to define the subset. Subtract the empty set you excluded and you have $7$. For any $n$, there are $2^n-1$ non-empty subsets of $n$ items by the same logic.

Related Question