Restricted Injective Assignments via the Multiplication Principle

Many konkur counting problems ask: in how many ways can we hand out distinct objects to distinct recipients so that no recipient gets an object it is forbidden? Each recipient gets at most one object and each object is used at most once — so we are counting injective assignments (also called systems of distinct representatives) subject to a forbidden-pairs table. The clean tool is the multiplication principle applied in the right order: fill the most-restricted slot first, then the next, accounting for objects already used.

The set-up

We assign one distinct object to each of the slots $s_1,\dots,s_k$ from a pool, where slot $s_j$ has an allowed set $A_j$ of size $a_j$ (the pool minus its forbidden objects). We want the number of injective maps $f$ with $f(s_j)\in A_j$ and $f(s_j)$ pairwise distinct.

The key idea: order the slots, then multiply

Process the slots from fewest allowed choices to most. When you reach a slot, its live count is its allowed size minus however many of those allowed objects were already consumed by earlier slots, so:

$\#\text{ways} \;=\; \prod_{j=1}^{k}\bigl(a_{(j)} - (\text{already-used objects that lie in }A_{(j)})\bigr),$

where $(1),(2),\dots$ is the order you chose. Starting with the tightest slot keeps the bookkeeping of "already-used" objects as small and as predictable as possible. Unrestricted slots (allowed set $=$ whole pool of size $n$) are always handled last: by then $t$ objects are gone, so such a slot contributes exactly $n-t$ — no case analysis needed.

When restricted slots overlap: split into cases

If two restricted slots share forbidden/allowed objects, "already-used" depends on which object the earlier slot took. The standard fix: case-split on the tight slots only (e.g. did the most-restricted slot take an object that the next restricted slot also wanted?), compute each case by the product rule, then add the cases. The unrestricted slots are multiplied in afterward as plain falling factors $n-t,\,n-t-1,\dots$.

How to apply (recipe)

1. Build the allowed-set table: for each slot list its forbidden objects and the size $a_j$ of what remains.
2. Sort slots by ascending $a_j$; the unrestricted ones go to the very end.
3. Place objects slot-by-slot, multiplying the live counts; case-split only where restricted allowed-sets interact.
4. Add the cases; the unrestricted tail contributes a falling-factorial $\,(n-t)(n-t-1)\cdots$.
5. If the recipients themselves are chosen from a larger set (e.g. pick $k$ of $m$ children), multiply by the relevant selection count or sum over the selections.

Mini-example

Give $3$ distinct prizes from $\{1,2,3,4\}$ to three slots $P,Q,R$, one each, where $P$ may not get prize $1$ and $Q$ may not get prize $1$; $R$ is unrestricted. Allowed sizes: $a_P=3$ ($\{2,3,4\}$), $a_Q=3$ ($\{2,3,4\}$), $a_R=4$.

Place the tight slots first. $P$ has $3$ choices from $\{2,3,4\}$. $Q$ must avoid $1$ and avoid $P$'s prize; since $P$ already took an allowed (non-$1$) prize, $Q$ has $3-1=2$ choices. Now $2$ objects are used, so unrestricted $R$ has $4-2=2$ choices:

$3\cdot 2\cdot 2 = 12.$

(Cross-check by inclusion–exclusion on $P,Q$ avoiding $1$: total injective $=4\cdot3\cdot2=24$; subtract those with $P=1$ ($1\cdot3\cdot2=6$) and $Q=1$ ($6$): $24-6-6=12$. Both agree.)

Exam trick: always fill the most-constrained slot first and push unrestricted slots to the end, where they collapse to a falling factorial $n-t,\,n-t-1,\dots$. If you start with an unrestricted slot you create needless cases; if you forget that distinct objects shrink later slots' counts, you over-count by treating the assignment as if repeats were allowed.