- Foundation
- About 14 min
- 5 practice questions
Choosing any number of items: subsets and the 2ⁿ rule
Count the selections of any size from n different items using 2ⁿ, handle "at least one" with 2ⁿ − 1, and count selections of even size or of items of different kinds.
If something looks wrong, please tell us.
So far we have chosen a fixed number of items, such as 3 from 10. Often the number is not fixed: a customer may choose any toppings, a teacher may choose any group of students. There is a clean answer for these questions, and it comes from looking at each item separately.
Each item is in or out
For each of n different items you decide yes or no: take it or leave it. The choices are independent, so by the multiplication principle there are 2 × 2 × … × 2 = 2ⁿ selections of any size, including taking nothing at all. Taking nothing is one selection, so the number of selections with at least one item is 2ⁿ − 1.
n different items give 2ⁿ selections of any size (including none) and 2ⁿ − 1 selections of at least one item.
Why this matches the combinations
A selection of size r can be made in ⁿCᵣ ways, so adding over all sizes gives ⁿC₀ + ⁿC₁ + … + ⁿCₙ = 2ⁿ. For n = 4 this is 1 + 4 + 6 + 4 + 1 = 16 = 2⁴. The row of Pascal's triangle adds up to a power of 2.
Worked example 1: fruit
A fruit stall has 5 different fruits. In how many ways can a customer choose some fruits (at least one)? The count is 2⁵ − 1 = 32 − 1 = 31. How many of these choices contain exactly one fruit? ⁵C₁ = 5. How many contain at least two fruits? Remove the empty choice and the 5 single choices: 32 − 1 − 5 = 26.
Worked example 2: selections of even size
From 5 different sweets, how many selections have an even number of sweets (including none)? Add the sizes 0, 2, 4: ⁵C₀ + ⁵C₂ + ⁵C₄ = 1 + 10 + 5 = 16, which is 2⁴. In general, the selections of even size are exactly half of all selections: 2ⁿ⁻¹. The same is true of odd sizes: ⁵C₁ + ⁵C₃ + ⁵C₅ = 5 + 10 + 1 = 16.
Worked example 3: one particular item must be taken
From 6 different books, a student must take the dictionary and may take any of the other five. The dictionary is fixed in, so only the other 5 books are in or out: 2⁵ = 32 choices. If the dictionary must be left out instead, the count is also 2⁵ = 32. If the dictionary may be taken or left, the count is 2⁶ = 64, and indeed 32 + 32 = 64.
Items of different kinds
Suppose a shop has 3 different shirts and 4 different ties. A customer picks some shirts and some ties, at least one item in all. For shirts alone there are 2³ = 8 selections including none, and for ties 2⁴ = 16 including none. Both together, with choices independent, give 8 × 16 = 128 including the empty choice, so the number with at least one item is 128 − 1 = 127. This equals 2⁷ − 1, because it is just 7 different items.
Identical items
If the items are identical, the count changes completely. From 5 identical coins, the number of selections of at least one is just 5 (take 1, 2, 3, 4 or 5 coins). In general, from n identical items the number of selections of at least one is n, and including none it is n + 1. Do not use 2ⁿ for identical items.
Key takeaways: each different item is in or out, so 2ⁿ selections of any size; subtract 1 to exclude the empty selection; a compulsory item removes one factor 2; for identical items the count is n or n + 1, not 2ⁿ.
Check your understanding
-
1. In how many ways can a non-empty group be chosen from 6 different people?
- 64
- 36
- 720
- 63
Show answer
Answer: D. There are 2⁶ = 64 selections including the empty one, so 64 − 1 = 63 non-empty groups.
-
2. From 7 different books, one particular book must be taken, and any of the others may be taken. How many choices?
- 128
- 64
- 127
- 49
Show answer
Answer: B. The compulsory book is fixed; each of the other 6 is in or out: 2⁶ = 64.
-
3. How many selections of even size (including none) are there from 4 different items?
- 16
- 4
- 8
- 15
Show answer
Answer: C. ⁴C₀ + ⁴C₂ + ⁴C₄ = 1 + 6 + 1 = 8, which is half of 2⁴.
-
4. From 5 identical oranges, how many selections of at least one are there?
- 5
- 31
- 32
- 10
Show answer
Answer: A. You can take 1, 2, 3, 4 or 5 oranges, which is 5 selections. 2ⁿ is used only for different items.
-
5. A shop has 3 different shirts and 4 different ties. How many non-empty selections of items are possible?
- 128
- 12
- 127
- 7
Show answer
Answer: C. The 7 items are all different, so 2⁷ − 1 = 127.
Sign in to keep track of the lessons you finish.