• 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. 1. In how many ways can a non-empty group be chosen from 6 different people?

    1. 64
    2. 36
    3. 720
    4. 63
    Show answer

    Answer: D. There are 2⁶ = 64 selections including the empty one, so 64 − 1 = 63 non-empty groups.

  2. 2. From 7 different books, one particular book must be taken, and any of the others may be taken. How many choices?

    1. 128
    2. 64
    3. 127
    4. 49
    Show answer

    Answer: B. The compulsory book is fixed; each of the other 6 is in or out: 2⁶ = 64.

  3. 3. How many selections of even size (including none) are there from 4 different items?

    1. 16
    2. 4
    3. 8
    4. 15
    Show answer

    Answer: C. ⁴C₀ + ⁴C₂ + ⁴C₄ = 1 + 6 + 1 = 8, which is half of 2⁴.

  4. 4. From 5 identical oranges, how many selections of at least one are there?

    1. 5
    2. 31
    3. 32
    4. 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. 5. A shop has 3 different shirts and 4 different ties. How many non-empty selections of items are possible?

    1. 128
    2. 12
    3. 127
    4. 7
    Show answer

    Answer: C. The 7 items are all different, so 2⁷ − 1 = 127.

Privacy · Terms · Refunds · Delivery