Why do I get one less than $2^k$?

Question

I have four letters, $A B C D$ , and I need all possible combinations when the order doesn't matter.

I thought this should be $2^k$ , with $ k$ being $4 $ .

But I can only count $15$, is there a reason for this? Am I missing one?

A
B
C
D
A,B
A,C
A,D
B,C
B,D
C,D
A,B,C
A,B,D
A,C,D
B,C,D
A,B,C,D

Don't you mean "I can only count 15" ??? – Sep 16 '19 at 08:23 — , Sep 16 '19 at 08:23

score 7 · Accepted Answer · answered Sep 16 '19 at 08:22

7

You are missing the combination containing no letters at all. A set of $k$ elements has $2^k$ subsets, but only $2^k - 1$ non-empty subsets.

answered Sep 16 '19 at 08:22

Mees de Vries

26,947

score 0 · Answer 2 · 2019-09-16T09:47:49.837

0

$2^k$ is due to the fact that you can take or not take the letters independently, so every binary choices multiply with each other. One of the combinations is "take none".

edited Sep 16 '19 at 09:47

answered Sep 16 '19 at 08:25

Why do I get one less than $2^k$?

2 Answers2