skip to content

Why does C(m+p, k) equal the sum over j of C(m, j) times C(p, k-j) when a roster splits into m platform engineers and p service owners?

level: seniorimportance: should knowfreq 33%

answer

  1. one roster, two disjoint pools
  2. ask how the set splits between them
  3. case-split on the platform headcount
  4. product rule inside a fixed case
  5. impossible cases contribute zero

basics

~20 s

Both sides count k-member reviewer sets on the combined roster. The right side splits that collection by how many members j come from the platform pool, then multiplies the choices within each pool. The split is a partition, so adding the cases reproduces the left side.

solid answer

~50 s

The left side counts k-member reviewer sets drawn from the whole roster of m + p people. The right side counts the same collection after a **case split on the mixture**: every such set contains some definite number j of platform engineers, and then exactly k - j service owners. For a fixed j the two pools are chosen independently, so the product rule gives `C(m,j) * C(p,k-j)` sets in that case. The cases are disjoint - a set cannot have two different platform headcounts - and they cover every possible j, so summing them recovers the whole collection. That is Vandermonde's identity. Two things make it work and both are worth saying out loud: the pools must **share no member**, or a set would split more than one way, and terms with j > m or k - j > p contribute 0 under the usual convention, which is why the sum can be written over all j without special cases.

go deeper

for a junior

Recognise the shape: a mixed selection from two separate groups can be counted by fixing how many come from the first group and multiplying the two choices. Remember that combining independent choices multiplies.

for a middle

Explain why the split is a partition and why the factors multiply rather than add, and know that the out-of-range terms are zero rather than errors. Being able to check a small case against the direct count is expected.

for a senior

Show you reach for the case split when a real count resists a direct attack - per-team minimums, mixed quorums, placements across shards - and that you state the disjointness hypothesis before using it rather than after it fails.

for a principal

Judge whether the model deserves the split at all. Two pools are a simplification of a roster with overlapping skills and availability; say what the count assumes, and what a decision resting on it therefore does not account for.

## The setting A roster is made of two disjoint pools: m platform engineers and p service owners. A review needs k people and does not care where they come from. How many k-member reviewer sets are there? Counted directly, the pools are irrelevant: there are m + p people and you choose k of them, so the answer is C(m+p, k). Counted through the split, you get a sum. Both are tallies of **one collection**, so they are equal - and that equality is Vandermonde's identity. ## The case split Take any k-member reviewer set and ask one question: **how many of its members are platform engineers?** Call that number j. Three properties make this a usable split: - **Definite** - every set has one specific j, because each member sits in exactly one pool. - **Disjoint** - a set with j = 2 is never also counted under j = 3, so no set is tallied twice. - **Exhaustive** - j ranges over 0 to k, and every set has some j in that range. Those three properties are the partition checks, and they are what licenses adding the cases up. ## Why the two factors multiply Within one case, building a set is two independent acts: choose which j of the m platform engineers are in, and choose which k - j of the p service owners are in. **Each platform choice can be paired with every owner choice**, and every pair gives a different reviewer set, so the case holds `C(m,j) * C(p,k-j)` sets. Adding instead of multiplying is the classic error here, and it answers a different question - the number of ways to make one choice **or** the other, not the number of combined sets. ## The boundary terms Written over all j from 0 to k, some terms describe impossible cases: j larger than m asks for more platform engineers than exist, and k - j larger than p asks the same of the other pool. Under the standard convention those coefficients are 0, so the impossible cases contribute nothing and no special-casing is needed. The sum is honest about its own range rather than needing guards around it. ## Worked case - 3 platform engineers, 4 service owners, k = 2 | j (platform) | k - j (owners) | C(3, j) | C(4, k-j) | sets in this case | |---|---|---|---|---| | 0 | 2 | 1 | 6 | 6 | | 1 | 1 | 3 | 4 | 12 | | 2 | 0 | 3 | 1 | 3 | | **total** | | | | **21** | And directly, C(7, 2) = 21. The two tallies agree, as they must. Notice the shape of the arithmetic: the mixed case dominates, which is the usual outcome and is why a sampling scheme that forces one pool to supply everybody is discarding most of the space. ## Where the identity is actually useful The value is not the formula; it is the **case split as a technique**. Whenever a collection is built from parts that do not overlap, conditioning on how much each part contributed turns one hard count into a sum of easy products. The same move handles: 1. a review that must draw from two teams, with a per-team minimum - drop the terms whose j violates the minimum; 2. a shard split where you count placements by how many land on one shard; 3. a specialisation of the identity worth recognising: set m = p = n and k = n, and the sum of C(n,j) * C(n,n-j) over j equals C(2n, n); using symmetry this is the sum of C(n,j)^2. For n = 2 that reads 1 + 4 + 1 = 6, which is C(4, 2). ## Where it stops applying The one hypothesis that matters is **disjointness of the pools**. If an engineer belongs to both, the question how many members are platform engineers no longer has a single answer for a given set, the cases stop being disjoint, and adding them over-counts. At that point the case split is simply the wrong instrument - not an instrument needing a correction factor. - The identity is a **partition plus the product rule**, nothing more exotic. - It requires no algebra to believe, and algebraic verification for small m, p, k is no substitute for the argument. - The zero convention is what keeps the summation range clean. - Overlapping pools break the hypothesis, not merely the arithmetic.

  • What does the identity specialise to when both pools have size n and you pick n reviewers?
    It gives the sum over j of `C(n,j) * C(n,n-j)` equal to C(2n, n), and applying the symmetry identity to the second factor turns it into the sum of the squares of a whole row: the sum of `C(n,j)^2` equals C(2n, n). Check it at n = 2: 1 + 4 + 1 = 6, and C(4, 2) = 6.
  • Why can the sum run over every j from 0 to k without guarding the impossible cases?
    Because a binomial coefficient whose lower index exceeds its upper index, or is negative, is 0 by convention. A term asking for more platform engineers than the pool holds therefore contributes nothing, and the same applies to the other pool. The convention is not a trick; it is the count of an empty case, which is genuinely zero.
  • What breaks if a few engineers belong to both pools?
    The case split stops being a partition. A set containing a dual-member engineer no longer has a single well-defined platform headcount, so it lands in more than one case and gets counted more than once, making the sum exceed C(m+p, k) - which is itself now the wrong left side, since the roster has fewer than m + p distinct people. You need a different counting rule, not a patched sum.

saying these in an interview costs you the question

  • Adds C(m,j) and C(p,k-j) instead of multiplying them
  • Applies the identity when the two pools share members
  • Thinks the cases can overlap, so some sets are counted twice
  • Treats terms with j above m as needing an explicit guard
  • Says the identity is algebraic coincidence with no counting meaning
  • Believes the left side must also be split by pool to be valid