Assign three labeled letters to three labeled envelopes, forbidding every letter’s own envelope. There are two valid assignments, the two three-cycles. Subtracting the three fixed-point counts from 3!=6 gives zero, which is wrong because assignments with multiple fixed points have been subtracted repeatedly. Inclusion–exclusion repairs the bookkeeping by tracking intersections, not by hoping violations rarely overlap.
Predict
Predict which forbidden-position selections can coexist in a permutation. Two selected cells in the same row demand two destinations for one letter, while two in the same column demand two letters in one envelope. Both are impossible. Compatible selected cells are exactly placements of nonattacking rooks on the forbidden board. Their number, rather than the total number of cell subsets, determines the sieve.
Experiment
For four diagonal forbidden cells, count compatible selected violations.
Selected cells k
Rook count r_k
Completions per placement
Signed contribution
0
1
24
24
1
4
6
−24
2
6
2
12
3
4
1
−4
4
1
1
1
Their sum is nine. Notice that selecting all four diagonal cells gives the identity permutation, whose multiple appearances must cancel correctly across the whole sum.
Understand
Let A_i be the event that position i is fixed. For a specified set of j fixed positions, the remaining n−j labels can be permuted freely, giving (n−j)! possibilities. Inclusion–exclusion yields D_n=Σ_j(−1)^j C(n, j)(n−j)!=n!Σ_j(−1)^j/j!. The empty permutation contributes D_0=1. Dividing by n! gives the probability of no fixed point under a uniform random permutation; the alternating-series remainder shows its distance from e^(−1) is at most 1/(n+1)!. This is an asymptotic statement with a quantitative bound, not an assumption that fixed-point events are independent.
Apply
For an arbitrary forbidden board B in an n-by-n array, let r_k count k nonattacking rooks on B and r_0=1. Inclusion–exclusion over forbidden cells contains many zero intersections. A nonzero intersection specifies k distinct rows and columns, leaving (n−k)! completions. Grouping by k gives the valid count Σ_k(−1)^k r_k(n−k)!. The rook polynomial R_B(t)=Σr_k t^k organizes these coefficients. If two board pieces use disjoint row sets and disjoint column sets, their rook polynomials multiply because placements can be selected independently. Disjoint cells alone do not suffice; shared rows or columns create conflicts.
Continue
Design a small restricted-assignment problem and verify its count by listing permutations before trusting the general formula. Then change one forbidden cell and explain which rook coefficients change. The method applies to labeled bijective assignments, not arbitrary functions that allow repeated targets. Large rook-number computations may themselves be difficult, so the sieve is a structural reduction rather than a universal fast algorithm. It becomes powerful when the forbidden board decomposes or has a manageable recurrence.
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
How many derangements of four labels exist?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
How many ways can two nonattacking rooks be placed on the three diagonal forbidden cells of a3×3 board?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Prove D_n=n!Σ from j0 to n of (−1)^j/j!.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove the forbidden-board countΣ(−1)^k r_k(n−k)!.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For forbidden cells (1, 1),(1, 2),(2, 1) on a3×3 board, find the valid permutation count.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Explain why D_n/n! approaches e^(−1).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
