How do you count the ways to place n distinct records into k named buckets with no bucket left empty?

## What is being counted A routing stage sends each of `n` distinguishable records to one of `k` named buckets - partitions of a work queue, output files, worker slots. The placements are all `k^n` of them, since each record independently picks a bucket. The constraint of interest is **coverage**: every bucket must receive at least one record, because an empty bucket means an idle consumer or a missing output. Counting the placements that achieve full coverage is counting **surjections** - onto functions - from records to buckets. ## Why the direct count is hard and the complement is easy There is no simple product formula for onto placements, because the constraint couples the records: whether the last record may go anywhere depends on what the earlier ones did. The complement is far more tractable. Fix a set of `j` buckets and ask for the placements that use **none** of them: every record has `k - j` remaining choices, so there are `(k-j)^n` such placements, and `C(k,j)` ways to choose which `j` buckets are avoided. Those counts are exact and independent of any ordering. ## Assembling the signed sum The sets overlap - a placement that uses only bucket 1 avoids buckets 2 and 3 at once, so it appears in several of the avoided-bucket counts - which is exactly what the alternation repairs: `onto(n, k) = sum over j from 0 to k of (-1)^j C(k,j) (k-j)^n` Worked for `n = 5`, `k = 3`: | j | C(3,j) | (3-j)^5 | signed term | |---|---|---|---| | 0 | 1 | 243 | +243 | | 1 | 3 | 32 | -96 | | 2 | 3 | 1 | +3 | | 3 | 1 | 0 | 0 | | total | | | **150** | A placement that uses only one bucket - say everything into bucket 1 - is subtracted twice by the `j = 1` group (once as avoiding bucket 2, once as avoiding bucket 3) and added back once by the `j = 2` group, so it is removed exactly once, as it should be. That is the alternation doing its job on a case you can check by hand. ## Two independent cross-checks 1. **Partition form.** Onto placements equal `k!` times the number of ways to split `n` records into `k` unlabelled non-empty groups, because naming the groups afterwards multiplies by `k!`. For `n = 5, k = 3` the unlabelled split count is 25, and `25 x 6 = 150`. 2. **Small case by hand.** For `n = 3, k = 2` the formula gives `8 - 2 x 1 = 6`, which is all eight placements minus the two that dump everything into one bucket. Enumerable in seconds, and a fast way to check you have the signs the right way round. ## Boundaries worth stating out loud - **If `n < k`, the count is zero**, and the formula produces zero on its own - no special case is needed. Some buckets must go empty when there are not enough records. - **If `n = k` it reduces to `n!`**, the assignments that put exactly one record in each bucket. - **Named versus unnamed buckets** is the distinction that most often breaks an answer. This formula counts placements into *distinguishable* buckets. If the buckets are interchangeable - an anonymous partition into `k` non-empty groups - divide by `k!`. - **Distinct versus identical records** matters just as much. If the records were interchangeable tokens, this is a completely different and much smaller count, and the exponential `k^n` would be wrong from the first line. ## Cost and why it is mild The sum has only `k + 1` terms, one per number of avoided buckets, because all `C(k,j)` subsets of the same size share a term value. That is the happy case of inclusion-exclusion: symmetry collapses `2^k` subsets into `k+1` groups. When the conditions are **not** symmetric - filters with different, unrelated match counts - no such collapse exists and the full `2^k` terms remain. Recognising which case you are in is what separates a formula-recall answer from an understanding one. ## Where it shows up Coverage counting underlies questions like how many distinct routings exercise every partition, or how likely a random assignment is to leave a consumer idle: divide the onto count by `k^n`. For `n = 5, k = 3` that is `150/243`, about 62 percent - so nearly two random routings in five would starve some bucket, which is why real routers assign deliberately rather than at random.