In the expansion of (1 + x)^n, why does the coefficient of x^k count the k-member reviewer sets drawn from n engineers?
answer
- one factor for each engineer
- every factor offers exactly two terms
- x means joining, 1 means staying off
- collect terms that share an exponent
- the exponent records the set size
basics
~20 sExpanding (1 + x)^n means one (1 + x) factor per engineer, and each factor contributes either 1 (stay off the review) or x (join it). A product becomes x^k exactly when k engineers contributed x, so its coefficient counts k-member sets.
solid answer
~50 sWrite the roster as one factor `(1 + x)` per engineer. Expanding by distributivity means forming every product that picks exactly one term out of each factor, so each expanded product is a decision string: `1` for an engineer who stays off the review, `x` for one who joins. A string with k copies of `x` multiplies out to `x^k`, and two different strings with the same k give the same monomial, so collecting like terms adds one unit to the coefficient of `x^k` for every k-member set. The coefficient is therefore a count, not a formula you have to derive first: it is the number of ways to choose which k of the n factors contributed `x`, which is exactly C(n, k). Nothing here requires x to be a number; it is a bookkeeping marker whose exponent records the size of the chosen set.
code
pseudocode · 10 linescoeffs = [1] // the polynomial 1, before any engineer is added
for each engineer in roster: // multiply the running polynomial by (1 + x)
next = array of zeros, length coeffs.length + 1
for k = 0 to coeffs.length - 1:
next[k] = next[k] + coeffs[k] // this engineer stays off the review
next[k + 1] = next[k + 1] + coeffs[k] // this engineer joins the review
coeffs = next
// coeffs[k] is now the number of k-member reviewer sets on the rostergo deeper
Remember the shape: n factors of (1 + x), each engineer choosing between two terms, and an exponent that records how many chose to join. The coefficient is a headcount of possibilities, not a formula to memorise.
Be able to run the expansion out loud: distributivity forms one product per decision string, like monomials are then collected, and the collecting step is the tally. Explain why order never enters, since each factor is consulted once.
Show that the reading survives a constraint change. If one engineer must be on the review, that factor loses its 1; if a pool cannot supply more than two, the surviving strings are the ones you count. Reason about the model, not the algebra.
Treat the expansion as a modelling choice you are accountable for. It assumes independent per-engineer decisions and interchangeable people; when either assumption is false in the real roster, say so before the count is quoted in a design decision.
## What the expansion actually is `(1 + x)^n` is not a formula waiting to be looked up; it is **n copies of the factor `(1 + x)` multiplied together**. Model a roster of n engineers by giving each engineer one factor. Expanding the product means applying distributivity until no parentheses remain, and distributivity has a precise combinatorial meaning: **the expanded sum contains one term for each way of picking exactly one summand out of every factor**. Each factor offers two summands, so before any like terms are collected there are 2^n products. Each of those products is a decision string over the roster: - pick `1` from an engineer's factor - that engineer **stays off** the review; - pick `x` from an engineer's factor - that engineer **joins** the review; - multiply the picks together - the `1`s vanish and the `x`s accumulate. A string that picked `x` from exactly k factors multiplies out to `x^k`. The exponent is therefore not an arbitrary label: **it is the size of the chosen reviewer set**. ## Why collecting like terms performs the count Two different decision strings can produce the same monomial. Choosing engineers A and B gives `x^2`; so does choosing C and D. Collecting like terms adds those contributions, so the coefficient of `x^k` accumulates **one unit per distinct set of k engineers**. | step in the algebra | what it means on the roster | |---|---| | one factor `(1 + x)` per copy | one engineer, faced with one binary decision | | picking a summand from each factor | building one candidate reviewer set | | the monomial `x^k` | that set has k members | | adding like `x^k` terms | tallying every distinct k-member set | | the coefficient of `x^k` | the number of k-member sets, C(n, k) | That is the whole argument, and it is worth noticing what it does **not** use. It never evaluates x. It never invokes a factorial expression. It never needs the coefficients computed in advance - the counting interpretation comes first, and any closed form for C(n, k) is a separate matter. ## Order does not enter The decision is made **per engineer**, not per position. There is no first pick or second pick, because each factor is consulted exactly once and independently. That is why the coefficient counts sets rather than sequences: two orderings of the same two engineers are not two different decision strings, they are the same string read twice. A candidate who reaches for an ordered count here has silently replaced the per-factor decision with a sequence of draws, which is a different process and a different number. ## Substituting values, and what each substitution says Because the identity holds as polynomials, it holds for every value of x, and each substitution turns the counting statement into an arithmetic one: 1. **x = 1** collapses every monomial to 1, so the sum of all the coefficients equals 2^n - the number of decision strings you started with. 2. **x = -1** makes the terms alternate, and the total is 0 for every n greater than 0, which says the k-member sets with k even and those with k odd are equally numerous. 3. **Two free symbols** generalise it: in `(a + b)^n`, picking `a` from k factors and `b` from the rest gives the term C(n, k)a^k b^(n-k), and the coefficient still counts which k factors contributed `a`. The third form is the binomial theorem in its usual dress, and the reading is unchanged: **a binomial coefficient in an expansion is always answering the question which factors contributed this symbol**. ## Why an interviewer asks this The payoff is not the polynomial. It is that a count you can only produce as a formula is a count you cannot check, while a count you can produce as a decision process is one you can argue about in a design review. An engineer who can say what x^k is recording can also tell you what happens when the model changes - engineers who must be included, pools that cannot mix, sizes that are capped - because those constraints change which decision strings survive, and the surviving strings are still visible in the expansion. - The exponent tracks **size**; the coefficient tracks **how many sets of that size exist**. - The 2^n pre-collection terms are the **decision strings**, not the answer. - Every substitution for x is a **different question asked of the same shelf of facts**. - The argument is stable under relabelling: nothing depends on which engineer got which factor.
- Why does the coefficient of x^k equal the coefficient of x^(n-k) in the same expansion?Because naming the k engineers who contributed `x` is the same act as naming the n-k engineers who contributed `1`. The two descriptions are two readings of one decision string, and the correspondence is one-to-one in both directions, so the tallies cannot differ. That is the symmetry identity C(n, k) = C(n, n-k), read as choose who is excluded.
- What does substituting x = -1 tell you about reviewer sets?Every term picks up a sign matching the parity of its size, and the total is (1 - 1)^n = 0 for any n above 0. So the number of even-sized reviewer sets equals the number of odd-sized ones on any non-empty roster. It is a counting statement obtained purely by evaluating an identity you already believe.
- How does the same argument give the coefficient in (a + b)^n?Each factor now offers `a` or `b` instead of `x` or `1`. A decision string that takes `a` from k factors multiplies to a^k b^(n-k), and the number of strings producing that monomial is the number of ways to choose which k factors gave `a`. So the term is C(n, k)a^k b^(n-k), and the coefficient still counts a choice of factors.
saying these in an interview costs you the question
- Thinks each x^k term comes from one factor rather than from k factors
- Says the coefficient counts ordered picks, so it should be n!/(n-k)!
- Believes the coefficients must be computed before they can be interpreted
- Assumes every expanded term is distinct, so all coefficients equal 1
- Insists x needs a numeric value before the expansion means anything