Learn / Library / Combinatorics

Capped lot allocations

CombinatoricsHard

A desk allocates $20$ identical lots among $4$ strategies. Each strategy gets a whole number of lots from $0$ to $8$ inclusive. How many allocations are there? Strategies are distinguishable.

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Count allocations without the cap, then remove those where some strategy exceeds it.

Solution

Without the cap there are $(3 23) = 1771$ allocations.
If a given strategy has at least $9$ lots, set those aside and share the remaining $11$ freely, giving $(3 14) = 364$ allocations; there are $4$ strategies, so $4 \times 364 = 1456$ are subtracted.
If $2$ given strategies both have at least $9$ lots, the remaining $2$ lots can be shared in $(3 5) = 10$ ways, and there are $6$ pairs; $3$ strategies would need at least $27$ lots, which is impossible.
The answer is $1771 - 1456 + 60 = 375$ .

Answer: $375$

Next question Back to the library