How many ways can 10 identical tickets be assigned to 4 named engineers?

## What makes this a distinct counting problem The defining features are that the **items are identical** and the **bins are distinct**. Ten support tickets that are interchangeable, four engineers who are not. Under those conditions an assignment is fully described by the tuple of counts `(x1, x2, x3, x4)` with `x1 + x2 + x3 + x4 = 10` and every `xi >= 0`. So the counting question becomes: how many non-negative integer solutions does that equation have? ## The stars-and-bars encoding Draw the 10 tickets as stars in a row and separate the four engineers' shares with 3 bars: ``` **|***||***** -> (2, 3, 0, 5) |*****|*****| -> (0, 5, 5, 0) **********||| -> (10, 0, 0, 0) ``` Every arrangement of 10 stars and 3 bars encodes exactly one assignment, and every assignment produces exactly one arrangement - a bijection. Empty groups (two adjacent bars, or a bar at an end) are legal and correspond to an engineer receiving nothing. Counting the arrangements is now easy: there are `10 + 3 = 13` positions, and choosing which 3 hold the bars determines everything. ``` C(13, 3) = (13 x 12 x 11)/(3 x 2 x 1) = 286 ``` ## The general formulas For `n` identical items into `k` distinct bins, using `k - 1` bars: ``` non-negative solutions: C(n + k - 1, k - 1) = C(n + k - 1, n) ``` If every bin must receive **at least one** item, pre-assign one item to each bin and distribute the remaining `n - k` freely. Substituting `yi = xi - 1` turns the constraint back into the non-negative case: ``` positive solutions: C(n - 1, k - 1) ``` Here that is `C(9, 3) = 84`. Note `84 < 286`, as it must be - the at-least-one requirement is a restriction. A lower bound other than 1 works the same way. "Each engineer gets at least 2" means pre-assigning 8 tickets and distributing 2 freely: `C(2 + 3, 3) = C(5, 3) = 10`. ## Sanity-check it on a case you can enumerate Three identical tickets, two engineers: the formula gives `C(3 + 1, 1) = 4`, and by hand the assignments are `(3,0), (2,1), (1,2), (0,3)` - four. Doing this check out loud in an interview is worth more than confidently quoting the formula, because the `n + k - 1` and `k - 1` slots are exactly where people mis-remember it. ## The same formula from a different direction Stars and bars is also the count for **unordered sampling with replacement**: choosing `k` items from `n` types where a type may be chosen repeatedly and only the multiset matters is `C(n + k - 1, k)`. The two statements are the same bijection viewed from either side - "how many of each type did I take" is exactly a tuple of non-negative counts summing to the number of picks. Being able to state that connection is a good signal. A caution carried over from that view: these outcomes are **not equally likely**. If the tickets were assigned by independent uniform random choice, each of the `4^10` distinguishable assignments would be equally likely, but the 286 count-tuples would not be - `(10,0,0,0)` arises one way while `(3,3,2,2)` arises in vastly more. Stars and bars answers a counting question, not a probability question. ## When it does not apply - **Distinguishable items, distinct bins:** each item independently picks a bin, giving `k^n`. Ten distinct tickets among 4 engineers is `4^10 = 1,048,576`, not 286. - **Identical items, identical bins:** now `(10,0,0,0)` and `(0,0,0,10)` are the same outcome and you are counting integer *partitions* of 10 into at most 4 parts. There is no simple closed form; this is a genuinely harder object. - **Upper bounds on a bin** ("no engineer takes more than 4") need inclusion-exclusion on top of stars and bars; the plain formula over-counts. ## Common mistakes 1. **Using `4^10`** when the items are identical - the single most common error, and it is off by four orders of magnitude. 2. **Writing `C(10, 4)`**, which counts choosing 4 things from 10 and has nothing to do with the question. 3. **Mis-placing the offsets** as `C(n + k, k)` or `C(n + k - 1, k)` in the bins framing - check against the 3-tickets-2-engineers case. 4. **Forgetting that bins may be empty**, or conversely applying the positive-solution formula when zeros are allowed. ## The compact answer "Identical items, distinct bins: stars and bars. Ten stars, three bars, thirteen positions, choose the bar positions: `C(13,3) = 286`. With everyone guaranteed one ticket, hand out four first and repeat on six: `C(9,3) = 84`."