Learn / Library / Combinatorics

Capped letter multisets

CombinatoricsHard

Build a multiset of size $6$ from $5$ letter types, using each type at most $3$ times. Letters of the same type are identical. How many different multisets are there?

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

Hint

Count all multisets, then remove those where some type appears too often.

Solution

Without any cap there are $(4 10) = 210$ multisets.
A bad multiset has some type used at least $4$ times; set those aside, leaving $2$ letters to place among $5$ types.
That gives $(4 6) = 15$ bad multisets per type, so $5$ types give $75$ .
No $2$ types can both be bad, since that needs $8 > 6$ letters.
Subtract: $210 - 75 = 135$ .

Answer: $135$

Next question Back to the library