# Math problem on combinations of components **URL:** \ **Category:** Factual Questions\ **Created:** [February 22, 2021, 4:30am UTC](https://boards.straightdope.com/t/math-problem-on-combinations-of-components/933430 "2021-02-22T04:30:13Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![MichaelEmouse](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/michaelemouse/32/101_2.png) [@MichaelEmouse](https://boards.straightdope.com/u/MichaelEmouse)\ **Post date:** [February 22, 2021, 4:30am UTC](https://boards.straightdope.com/t/math-problem-on-combinations-of-components/933430/1 "2021-02-22T04:30:13Z")
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? ---
**Author:** ![Hypnagogic\_Jerk](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hypnagogic_jerk/32/4252_2.png) [@Hypnagogic\_Jerk](https://boards.straightdope.com/u/Hypnagogic_Jerk)\ **Post date:** [February 22, 2021, 4:56am UTC](https://boards.straightdope.com/t/math-problem-on-combinations-of-components/933430/2 "2021-02-22T04:56:10Z")
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. ---
**Author:** ![MichaelEmouse](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/michaelemouse/32/101_2.png) [@MichaelEmouse](https://boards.straightdope.com/u/MichaelEmouse)\ **Post date:** [February 22, 2021, 5:25am UTC](https://boards.straightdope.com/t/math-problem-on-combinations-of-components/933430/3 "2021-02-22T05:25:09Z")
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. ---
**Author:** ![Hypnagogic\_Jerk](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hypnagogic_jerk/32/4252_2.png) [@Hypnagogic\_Jerk](https://boards.straightdope.com/u/Hypnagogic_Jerk)\ **Post date:** [February 22, 2021, 5:47am UTC](https://boards.straightdope.com/t/math-problem-on-combinations-of-components/933430/4 "2021-02-22T05:47:50Z")
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. ---
**Author:** ![Buck\_Godot](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/buck_godot/32/6573_2.png) [@Buck\_Godot](https://boards.straightdope.com/u/Buck_Godot)\ **Post date:** [February 22, 2021, 5:48am UTC](https://boards.straightdope.com/t/math-problem-on-combinations-of-components/933430/5 "2021-02-22T05:48:25Z")
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. ---
**Author:** ![MichaelEmouse](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/michaelemouse/32/101_2.png) [@MichaelEmouse](https://boards.straightdope.com/u/MichaelEmouse)\ **Post date:** [February 22, 2021, 5:52am UTC](https://boards.straightdope.com/t/math-problem-on-combinations-of-components/933430/6 "2021-02-22T05:52:04Z")
You’re right. Thanks. ---
**Author:** ![LSLGuy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lslguy/32/5813_2.png) [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)\ **Post date:** [February 23, 2021, 3:02am UTC](https://boards.straightdope.com/t/math-problem-on-combinations-of-components/933430/7 "2021-02-23T03:02:26Z")
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.