Inclusion–exclusion, onto functions and derangements
Objectives and prerequisites
Build bad-event sets, count their intersections, apply inclusion–exclusion with correct multiplicities, and use the method for onto functions, missing symbols and fixed points of permutations. Prerequisites: finite sets, function terminology, combinations and permutations. This lesson deepens the earlier two-/three-set rule rather than introducing another unrelated formula list.
Every event in this lesson is a subset of one specified finite universe. Counts are not automatically probabilities. When a probability is requested, divide by the universe size only if the outcomes are equally likely under the stated random experiment.
1. Why alternating intersection counts work
For sets A₁,…,A_k, the union count is the sum of single-set sizes, minus all pairwise intersection sizes, plus all triple intersections, and so on. The sign of an intersection of j distinct events is (−1)^{j+1}. The count outside their union starts from the universe size and uses signs (−1)^j, including the empty selection of events.
Why? An object that belongs to exactly t≥1 events appears C(t,1) times in singles, C(t,2) times in pairs and so on. Its total union contribution is C(t,1)−C(t,2)+⋯+(−1)^{t+1}C(t,t)=1, because Σ(j=0 to t)(−1)^j C(t,j)=(1−1)^t=0. An object in no event contributes zero to the union. This accounts for each object exactly once.
This proof exposes two common errors. Subtracting all bad sets without adding their intersections can remove an object more than once. Conversely, pairwise intersections usually include objects in triple intersections; do not silently replace inclusive intersections by “exactly these two” counts.
2. Worked arithmetic universe
Let U={1,2,…,120}. Define A as multiples of 2, B as multiples of 3 and C as multiples of 5. Their sizes are 60,40,24. An intersection means simultaneous divisibility, so use the least common multiple: |A∩B|=floor(120/6)=20, |A∩C|=12, |B∩C|=8, and |A∩B∩C|=4.
The union count is 60+40+24−20−12−8+4=88. Therefore exactly 120−88=32 integers are divisible by none of 2,3,5. Here the divisors are pairwise coprime, but the general rule is lcm, not always product. For divisibility by 4 and 6, the intersection divisor is 12, not 24.
The wording “or” is inclusive in a union: numbers satisfying two or all three properties are included. “Exactly one” is a different target and needs different coefficients.
3. Exactly one, exactly two, at least two
For three events, write S₁=|A|+|B|+|C|, S₂=|A∩B|+|A∩C|+|B∩C| and S₃=|A∩B∩C|. Then:
- Exactly three: S₃.
- Exactly two: S₂−3S₃.
- At least two: S₂−2S₃.
- Exactly one: S₁−2S₂+3S₃.
Derive rather than guess. An object in exactly two events appears twice in S₁ and once in S₂. An object in all three appears three times in S₁ and three times in S₂. Substituting these contributions into the formulas gives either 0 or 1 according to the requested category.
For the divisibility example, S₁=124,S₂=40,S₃=4. Exactly two gives 40−12=28; at least two gives 40−8=32; exactly one gives 124−80+12=56. The disjoint categories exactly one, exactly two and exactly three sum to 56+28+4=88, checking the earlier union. The number outside is also 32, but that equality is an accident of these data, not a theorem.
4. Onto functions: exclude missing targets
Let the domain contain n labeled elements and the codomain k labeled elements, with n,k≥1. There are kⁿ total functions. For each codomain element i, define A_i to be functions that never use target i. A function is onto exactly when it lies in none of the A_i.
If a specified set of j targets is missing, each domain element has k−j remaining choices, so the intersection count is (k−j)ⁿ. There are C(k,j) ways to choose that missing set. Inclusion–exclusion gives the onto count
Σ(j=0 to k)(−1)^j C(k,j)(k−j)ⁿ.
For n=4,k=3, the answer is 3⁴−3·2⁴+3·1⁴−0⁴=81−48+3=36. This does not count injections: four domain elements cannot inject into three targets, but many onto functions exist. If k>n, no onto function exists because too few domain elements are available to hit every target; the sum is then zero.
The case n=k reduces to k!, because onto between two equally sized finite sets is equivalent to one-to-one. For positive n and k=1, there is exactly one onto function. Empty-domain/codomain cases should be handled directly from the definition rather than inserted into this lesson's positive-parameter formula without conventions.
5. Exactly a specified number of used symbols
A length-n word over a k-symbol alphabet is a function from n labeled positions to the symbols. For n,k≥1 and 1≤r≤min(n,k), to use exactly r distinct symbols, first choose the used set in C(k,r) ways and then count onto functions from the n positions to those r symbols. Different chosen sets give disjoint collections of words, so multiplication is justified.
Example: length-4 words over {A,B,C,D} using exactly two symbols number C(4,2)(2⁴−2)=6·14=84. Once the two symbols are chosen, subtract the two constant words. The sequence ABAB differs from BABA because positions are labeled. Choosing two symbols and multiplying by 2⁴ without subtraction would wrongly include words using only one symbol.
Onto labeled boxes also connect to partitions into unlabeled nonempty groups. For four distinct objects split into three nonempty unlabeled groups, each partition has 3! ways to label its groups. Thus the count is 36/6=6. Independently, exactly one group has two elements and the others are singletons; choose that pair in C(4,2)=6 ways. This division works because all three groups are nonempty and their labels can be assigned in exactly 3! ways.
6. Derangements: no fixed point
A permutation π of {1,…,n} is a bijection. A fixed point is an index i with π(i)=i. A derangement has no fixed points. Let D_n count them. Define A_i as permutations fixing i. If a specified j-element set is fixed, the remaining n−j elements can be permuted in (n−j)! ways; other elements may also be fixed because an intersection is inclusive.
Inclusion–exclusion yields
D_n=Σ(j=0 to n)(−1)^j C(n,j)(n−j)!=n! Σ(j=0 to n)(−1)^j/j!.
For four objects, D₄=24−4·6+6·2−4·1+1=9. Removing the four single fixed-point sets from 24 without restoring intersections would give zero, which is incorrect. For five objects, D₅=120−120+60−20+5−1=44. Thus permutations with at least one fixed point number 120−44=76.
Use D₀=1: the empty permutation is the unique permutation with no fixed point. D₁=0, because the only one-element permutation fixes its element. These conventions make later exact-fixed-point formulas work at the endpoints.
7. Exactly r fixed points
To have exactly r fixed points among n labels, choose their set in C(n,r) ways and derange the remaining n−r labels. The count is C(n,r)D_{n−r}. The remaining permutation must be a derangement relative to those labels; using (n−r)! would permit extra fixed points and count “at least these r” instead.
For n=5 and exactly two fixed points, the answer is C(5,2)D₃=10·2=20. The two derangements of a three-label set are its two 3-cycles. Exactly four fixed points among five is impossible: the sole remaining label is forced to itself, reflected by C(5,4)D₁=0. Exactly five fixed points gives C(5,5)D₀=1.
As a consistency check, Σ(r=0 to n)C(n,r)D_{n−r}=n!, since every permutation has a unique number and set of fixed points. Disjoint cases can safely be added; overlapping fixed-point events require inclusion–exclusion.
Problem-solving checklist
Name one universe and define each bad event precisely. Count an intersection for a specified selected set of events before multiplying by the number of such selections. Distinguish “none,” “at least one,” “exactly one” and “exactly r.” Keep onto functions, injections and permutations separate. If a result is negative, exceeds the universe, or fails a tiny hand-enumerated case, revisit the event model rather than patching arithmetic.
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option and retain all stated label, symmetry, domain and positivity assumptions.
C01. Among integers 1 through 120, how many are divisible by none of 2,3,5?
A. 88 B. 36 C. 32 D. 28
Answer: C
A: 88 is the union, integers divisible by at least one of the three.
B: This does not use the correct pair and triple intersections.
C: The union is 60+40+24−20−12−8+4=88; its complement is 120−88=32.
D: 28 counts integers divisible by exactly two of the three, not none.
C02. For the same divisibility sets in 1,…,120, how many integers satisfy exactly one of divisibility by 2,3,5?
A. 56 B. 88 C. 84 D. 64
Answer: A
A: Using S₁=124,S₂=40,S₃=4, exactly one is S₁−2S₂+3S₃=56.
B: This is the inclusive union and still counts double/triple members.
C: S₁−S₂=84 gives a triple member net contribution zero but still counts double members once. It is not exactly one.
D: This fails the multiplicity correction; exactly-one objects should contribute one, all double/triple objects zero.
C03. How many onto functions map a four-element labeled domain to a three-element labeled codomain?
A. 81 B. 24 C. 0 D. 36
Answer: D
A: 81=3⁴ counts all functions, including those missing targets.
B: 4! counts permutations of four labels, a different function model.
C: Zero is the injection count here, not the onto count.
D: Exclude missing targets: 3⁴−3·2⁴+3·1⁴=36. Overlapping missing-target events require the positive correction.
C04. How many length-4 words over {A,B,C,D} use exactly two distinct symbols?
A. 96 B. 84 C. 14 D. 144
Answer: B
A: C(4,2)·2⁴ includes constant words that use only one chosen symbol.
B: Choose the two symbols in 6 ways and use both in 2⁴−2=14 ways, giving 84.
C: 14 is the count for one fixed pair of symbols, before choosing which pair.
D: There are 6 possible used pairs and 14 valid words per pair, not 24; 144 does not count the stated class.
C05. How many derangements are there on four labeled elements?
A. 24 B. 0 C. 9 D. 6
Answer: C
A: 24 counts all permutations, including those with fixed points.
B: Subtracting all four single fixed-point events without restoring intersections gives this incorrect result.
C: D₄=24−4·6+6·2−4+1=9 by inclusion–exclusion.
D: 6 is the number of 4-cycles, but derangements also include three permutations made of two disjoint swaps.
C06. How many permutations of five labeled elements have exactly two fixed points?
A. 20 B. 60 C. 10 D. 44
Answer: A
A: Choose the two fixed labels in C(5,2)=10 ways and derange the remaining three in D₃=2 ways, giving 20.
B: 10·3! allows extra fixed points among the remaining labels and overcounts the requested class.
C: 10 chooses only the fixed set and omits the two possible derangements of the remaining labels.
D: 44 is D₅, the no-fixed-point count, not the exactly-two count.
Sources and scope
This original lesson deepens combinatorial counting within Discrete Mathematics in Section 1 of the official GATE 2027 CS syllabus. The official syllabus establishes the broad area; the MIT chapter provides institutional further-study support for counting methods. Examples, explanations and practice here are original. One lesson is not a claim of entire-subject mastery.
Sources opened and checked 2026-10-14.
Sign in to keep your progress. Sign in