skip to content

On an n-engineer roster, why does summing the number of possible reviewer sets of every size 0 through n give exactly 2^n?

level: middleimportance: must knowfreq 50%

answer

  1. count one collection twice
  2. the collection is every possible set
  3. organise by size, then by engineer
  4. bins must be disjoint and cover everything
  5. two tallies of one shelf must agree

basics

~20 s

Both totals count one collection: every reviewer set the roster can produce. Grouping that collection by size and adding the groups gives the sum of binomial coefficients; building a set by deciding in or out per engineer gives 2^n. One collection, two tallies, so they are equal.

solid answer

~50 s

Fix the collection first: **all** reviewer sets drawable from the roster, the empty one and the full one included. Tally it once by size - every set has exactly one size, so the sizes 0 through n cut the collection into disjoint parts that miss nothing, and adding the part sizes gives C(n,0) + C(n,1) + ... + C(n,n). Tally it again by construction - walk the roster and decide in or out for each engineer, which is 2 choices repeated n times and reaches every set exactly once, giving 2^n. Neither tally changed the collection, so the two numbers must agree. That is the whole method: **name one finite collection, count it under two organising schemes, and conclude the results are equal** - no algebra and no induction required, which is why the argument also explains why the identity is true rather than merely that it is.

go deeper

for a junior

Hold on to the shape of the claim: add up how many reviewer sets exist at each size and you get the number of in-or-out decisions over the roster. Remember that the empty review counts as a set.

for a middle

Be able to give both tallies and say what makes each legitimate: sizes partition the collection, and the per-engineer decision reaches every set exactly once. Naming the partition checks is what separates an explanation from an assertion.

for a senior

Demonstrate you can rerun the argument under a changed model - a mandatory reviewer, a forbidden empty review, a size cap - and get the new count without searching. That is the skill the identity is standing in for.

for a principal

Decide when a counting argument is worth asking for at all. A brute-force check is cheaper and often sufficient; insist on the argument when the count will be extrapolated to a larger n or reused after the model changes.

## Name the collection before you count it The mistake that sinks this question is starting with the formula. Start with the **object**: the collection of every reviewer set the roster can produce. On a four-engineer roster that collection has a definite membership - the empty set, the four single-engineer sets, the six pairs, the four triples, and the whole roster. Nothing about that collection changes during the argument. Both tallies below are tallies of **that one shelf of objects**, and that is the only reason the identity holds. ## Scheme one - organise by size Sort the collection into bins labelled 0 through n by how many engineers each set contains. - Every set lands in **exactly one** bin, because a set has one size. - No set is **missed**, because every size from 0 to n is a bin. - The bin labelled k holds C(n, k) sets by definition of what that coefficient counts. Adding the bins gives C(n,0) + C(n,1) + ... + C(n,n). Those two properties - disjoint bins and full coverage - are what make it a **partition**, and a partition is the only kind of split you are allowed to add up. ## Scheme two - build each set by walking the roster Now count the same shelf by describing how a set is produced. Walk the roster once, and for each engineer record **in** or **out**. That is 2 options repeated n times, so there are 2^n records, and the correspondence with sets runs both ways: - every record produces one reviewer set; - every reviewer set, including the empty one, is produced by exactly one record. So the shelf has 2^n items. ## Why the two answers must agree Nothing moved between the tallies. One finite collection cannot have two different sizes, so C(n,0) + C(n,1) + ... + C(n,n) = 2^n. This is the **counting one set two ways** method, and it is worth stating in its general form because it is the reusable part: 1. **Name a single finite collection** precisely enough that membership is decidable. 2. **Count it under one organising scheme**, checking that the scheme partitions rather than overlaps. 3. **Count it under a second, unrelated scheme**, with the same check. 4. **Equate the two counts** - the identity is the conclusion, not the starting point. | the identity's side | the scheme it comes from | the check it needs | |---|---|---| | sum of C(n, k) over k | group the sets by size | sizes are disjoint and cover 0 to n | | 2^n | decide in or out per engineer | every set is produced exactly once | ## The four-engineer case, in full | size k | sets of that size | count | |---|---|---| | 0 | the empty review | 1 | | 1 | one engineer reviews | 4 | | 2 | a pair reviews | 6 | | 3 | one engineer sits out | 4 | | 4 | the whole roster reviews | 1 | | total | | **16 = 2^4** | The row 1, 4, 6, 4, 1 sums to 16, which is 2^4. Drop the empty set from the model and you get 15, not a power of two - which is exactly the point that the bins must **cover** the collection, edge cases included. ## Why this beats checking values An engineer who verifies the identity for n up to 20 has established 20 facts and no reason. A double-counting argument establishes the general statement and, more usefully, tells you what to do when the situation changes: - **Forbid the empty review and the full roster** and the same argument gives 2^n - 2, because the construction scheme reaches exactly two records you are now excluding. - **Force one named engineer onto every review** and that engineer's decision disappears; the construction scheme has n-1 free decisions, so the total is 2^(n-1). - **Cap the review at size two** and the size scheme simply stops after its third bin, while the construction scheme no longer has a clean form - which tells you which of the two views to keep. Each of those follows from the structure of the argument, not from re-deriving anything. That transferability is why an interviewer probes the argument rather than the value. ## The traps - Forgetting that the empty set and the full roster are genuine members of the collection. - Adding groups that **overlap**, which double-counts and is the most common way a counting argument silently fails. - Confusing 2^n with the number of orderings of the roster, which is a different construction entirely. - Treating double counting as informal because it has no algebra in it; it is a proof, and the rigour lives in the disjoint-and-covering checks.

  • What exactly must you verify for the group-by-size half of the argument to be valid?
    That the groups partition the collection: every reviewer set has **exactly one** size, so no set appears in two groups, and the labels 0 through n leave no set homeless. Disjointness stops double counting and coverage stops omission. Adding group sizes is only legitimate once both checks pass - an overlapping split is the usual way one of these arguments quietly produces a wrong number.
  • A colleague verifies the identity by brute force for every n up to 20. What does the counting argument give that the check does not?
    Generality and transferability. The check confirms 20 instances and says nothing about n = 21 or about any variant. The argument says **why** the two sides agree, so when the model changes - excluding the empty review, pinning one engineer on, splitting the roster - you can rerun the reasoning and get the new count instead of rerunning the search.
  • How does the total change if the empty review and the full-roster review are both disallowed?
    It becomes 2^n - 2. The construction scheme produces one record per set, and exactly two of those records are the ones now excluded, so the shelf loses two items. The size scheme agrees: you are dropping the two end bins, each of which holds exactly one set, since C(n,0) and C(n,n) are both 1.

Count a seated audience by rows, then count it again by columns. Nobody stood up between the two tallies, so the two numbers have to agree - and that forced agreement, not the arithmetic, is the entire content of a double-counting proof.

saying these in an interview costs you the question

  • Says the sides are equal because the numbers match for small n
  • Thinks the size groups overlap, so the sum double-counts sets
  • Forgets the empty review and the full roster are genuine sets
  • Claims 2^n counts orderings of the roster rather than subsets
  • Treats double counting as a hand-wave rather than a proof
  • Asserts the identity needs induction before it can be believed