Did you know? Four distinct students can be assigned to three different project teams in 81 ways if empty teams are permitted—but only 36 assignments put at least one student in every team. The difference comes from subtracting all the assignments that leave a team empty, then correcting for assignments that have been subtracted more than once.
That is the core of counting surjective (onto) functions. For JC2 students considering a Mathematics tutor in Bukit Timah, this is an unusually useful enrichment application of the Singapore–Cambridge H3 Mathematics (9820) content: the bijection and inclusion–exclusion principles, H2 counting knowledge, and precise proof by cases.
Quick answer: The number of onto functions from an n-element labelled domain to a k-element labelled codomain, with n≥1 and k≥1, is Σ from j=0 to k of (−1)^j C(k,j)(k−j)^n. If n<k, an onto function is impossible. The formula counts all functions and subtracts those missing at least one target, correcting overlapping omissions.
What is an onto function?
A function f:A→B assigns each element of A exactly one image in B. The function is surjective, or onto, when every element of B receives at least one preimage. The requirement concerns the entire codomain, not just the image of a particular input.
For a finite domain with n distinct elements and a codomain with k distinct elements, there are k choices for each domain element. Thus there are k^n total functions when no target-coverage condition is imposed.
A function cannot be onto when n<k, because fewer than k domain elements cannot occupy k distinct outputs. This is a direct counting obstruction, closely related to the pigeonhole principle.
Suppose n=k. If the function is onto, each of the k targets must be hit exactly once. The function is then a bijection and there are k! choices, the number of permutations.
Surjection and injectivity are different. A surjection may send two different domain elements to the same codomain value, provided every codomain value is reached. An injection may leave some codomain values unused when the codomain is larger than the domain.
Translate the mathematical wording to a practical model: distinct students are the labelled domain objects, and labelled teams are the codomain. Every team being nonempty is exactly the onto condition. If students or teams are indistinguishable, the counting model changes.
The inclusion–exclusion proof
Begin with all k^n functions from an n-element domain to a k-element codomain. For each codomain target i, let E_i be the collection of functions that never take value i. The forbidden outcome is an assignment in at least one E_i.
If a specific target is omitted, every domain element has only k−1 permitted outputs, so |E_i|=(k−1)^n. There are k possible omitted targets, and subtracting all k such sets removes k(k−1)^n assignments.
But a function omitting two targets has been subtracted twice. For each specified pair of omitted targets, there are (k−2)^n functions. Add these back, across C(k,2) possible omitted pairs.
Continue alternating signs to correct functions that omit three or more targets. This is precisely the inclusion–exclusion principle. The result is T(n,k)=Σ_{j=0}^k (−1)^j C(k,j)(k−j)^n, where T denotes the number of surjections.
The formula is valid for n≥1,k≥1 without needing a convention for 0^0. For n<k it evaluates to zero as it must, although the direct impossibility argument is often clearer.
Each term has a concrete meaning. The binomial coefficient C(k,j) chooses which j targets are missing, while (k−j)^n counts functions into the remaining target set. The alternating sign corrects overcounting among overlapping omission events.
A correct combinatorial proof should describe the missing-target sets before displaying the formula. Merely expanding the summation gives arithmetic without explaining what is being counted.
Worked example: four students, three labelled teams
Let the students be A,B,C,D and the teams be Red, Blue and Green. Each student must join exactly one team; every team must have at least one member. We count assignments, not arrangements within a team.
Without the nonempty requirement there are 3^4=81 functions. Assignments missing a particular team have 2^4=16 possibilities. There are three possible missing teams, so subtract 3×16=48.
Assignments missing two particular teams send every student to the one remaining team; there is one such function for each of three pairs of missing teams. Add back three. No function from a nonempty domain can omit all three targets.
Therefore T(4,3)=81−48+3=36. The calculation can be checked by a different classification, which makes the result more convincing.
With four students and three nonempty teams, exactly one team has two students and the other two have one each. Choose the double-occupancy team in three ways, choose its two students in C(4,2)=6 ways, and assign the remaining two students to the other labelled teams in two ways.
The product is 3×6×2=36. This is a direct counting proof that agrees with inclusion–exclusion. The two methods enumerate the same assignments from different viewpoints.
These assignments are not stars-and-bars patterns. Students are distinct. Swapping student A with student B may create a different function even when team sizes remain the same. That distinction is central to choosing the correct method.
Distinguishable objects and distinguishable boxes
Suppose eight identical counters are put in three labelled boxes, with empty boxes permitted. The number of count triples is C(8+3−1,3−1)=C(10,2)=45 by stars and bars. That question tracks only box occupancies.
For eight different labelled objects, there are 3^8 possible assignments with empty boxes allowed. Reassigning two distinct objects changes the function even if occupancy counts stay the same.
If each box must be nonempty, the labelled-object count is T(8,3)=3^8−3·2^8+3=6561−768+3=5796. The identical-object count with each box nonempty is C(7,2)=21, a much smaller number.
Neither result is universally ‘more correct’. They answer different questions. A tutor should insist that the learner describes the objects, whether labels matter and whether empty groups are permitted before selecting a formula.
If the boxes are unlabelled, permuting team names does not create a new allocation. When all k boxes must be nonempty, dividing the labelled surjection count by k! gives the number of partitions of n distinct objects into k nonempty unlabelled groups. This is known as a Stirling number of the second kind.
The division is justified because every unlabelled partition into k nonempty blocks has exactly k! different assignments of labels to its blocks. No two block labels are interchangeable without changing a labelled surjection.
A recurrence as a second way to count
Let T(n,k) count surjections from n labelled objects to k labelled targets. Consider the last domain element. Its target might already be occupied by the first n−1 elements, or it might be the only member assigned to that target.
In the first case, the first n−1 elements must already occupy all k targets: T(n−1,k) choices. The last element can choose any of k targets, giving kT(n−1,k).
In the second case, choose which one of the k targets is used only by the last object. The first n−1 elements must surject onto the remaining k−1 targets, yielding kT(n−1,k−1) choices.
These cases are disjoint and exhaustive. Therefore T(n,k)=kT(n−1,k)+kT(n−1,k−1) for appropriate positive n and k, with T(n,1)=1 and T(n,n)=n!.
Check T(4,3): 3T(3,3)+3T(3,2)=3×6+3×6=36. This agrees with the inclusion–exclusion count and the occupancy classification.
The recurrence is valuable because it exposes the structure of onto assignments, rather than relying only on an alternating sum. It also builds on the existing recurrence relations and induction guide.
To use the recurrence in a proof, name the two cases precisely. Avoid saying ‘last element goes anywhere’ without noting whether all earlier target values are already covered.
The probability that every team is occupied
Suppose each of n distinct objects is assigned independently and uniformly to one of k labelled targets. All k^n functions are equally likely. The event that every target receives at least one object is the event that the random function is onto.
Therefore the probability is T(n,k)/k^n. For n=4,k=3, this is 36/81=4/9. A probability is between zero and one because T(n,k) counts a subset of all functions.
For n=3,k=2, there are 2^3=8 total assignments and T(3,2)=6 onto assignments, so the probability is 3/4.
These probabilities depend on the independent uniform-assignment model. If objects prefer certain boxes, the functions are not equally likely, so dividing favourable counts by k^n would be invalid.
An adjacent but different question asks for the expected number of occupied boxes. Its answer under the same independent uniform model is k[1−(1−1/k)^n], obtained by indicator variables. Expected occupied count is not the same as the probability every box is occupied.
The indicator-variable guide explains that expectation method. Here the focus is the exact count of complete target coverage.
A proof and modelling checklist
Before calculating, state n and k, confirm whether they are positive integers, and identify what counts as a distinct domain object and a distinct target. Determine whether every target must be used.
If the objects are distinct and targets labelled, think functions. If objects are indistinguishable and only occupancies matter, think stars and bars. If targets are unlabelled, a partition or Stirling-number model may be appropriate.
For onto functions, count all assignments and apply inclusion–exclusion to the sets of functions omitting each target. Explain why a particular intersection of omitted-target events has (k−j)^n members.
Check the boundary n<k: no onto function exists. If n=k, every onto function is a bijection and the count is k!. If k=1 and n≥1, exactly one function exists and it is onto.
Use a small example to verify the summation, but do not substitute a list of sample values for a general proof. The inclusion–exclusion argument explains why the formula works for arbitrary positive n and k.
Treat surjections as a connected advanced counting application rather than a standalone guaranteed H3 examination topic. The official syllabus explicitly names bijection and inclusion–exclusion, and these examples make both principles concrete.
The immutable eduKateSG small-group Mathematics reference describes a three-learner Secondary 1 tutorial model near Sixth Avenue MRT. It does not confirm currently available JC2 H3 places. Enquire about advanced Mathematics tuition directly.
60 original onto-function and counting clinics
1. One target
Question: How many onto functions are there from three distinct inputs to one target?
Worked result: Exactly one: each input must map to the only target.
Reasoning check: For a nonempty finite domain, a one-target function is automatically onto.
2. Two targets, two inputs
Question: How many onto functions exist when n=k=2?
Worked result: Two: the two permutations of the targets.
Reasoning check: When n=k, being onto forces a bijection.
3. Two targets, three inputs
Question: Evaluate T(3,2).
Worked result: 2³−2=6, since the two constant functions miss a target.
Reasoning check: Subtract a function for each missing target; no additional intersections arise for a nonempty domain.
4. Two targets, four inputs
Question: Evaluate T(4,2).
Worked result: 2⁴−2=14. Every nonconstant binary assignment reaches both targets.
Reasoning check: Onto a two-element target set means that both labels appear at least once.
5. Two targets, five inputs
Question: Evaluate T(5,2).
Worked result: 2⁵−2=30.
Reasoning check: The two excluded assignments put all five inputs into one target.
6. Two targets, six inputs
Question: Evaluate T(6,2).
Worked result: 2⁶−2=62.
Reasoning check: The simple two-target formula follows directly from complement counting.
7. Three targets, two inputs
Question: Can a function from two distinct inputs be onto a three-element target set?
Worked result: No. Two inputs can hit at most two distinct target values.
Reasoning check: The pigeonhole principle rules out all cases n<k.
8. Three targets, three inputs
Question: Evaluate T(3,3).
Worked result: 3!=6, since each target must receive exactly one input.
Reasoning check: Onto and injective are equivalent when the finite domain and codomain have equal size.
9. Three targets, four inputs
Question: Evaluate T(4,3).
Worked result: 3⁴−3·2⁴+3=81−48+3=36.
Reasoning check: The plus-three term restores assignments omitted twice in the first correction.
10. Three targets, five inputs
Question: Evaluate T(5,3).
Worked result: 3⁵−3·2⁵+3=243−96+3=150.
Reasoning check: The formula counts labelled assignments satisfying every target.
11. Three targets, six inputs
Question: Evaluate T(6,3).
Worked result: 3⁶−3·2⁶+3=729−192+3=540.
Reasoning check: A very large outcome space can be reduced to a few intersection counts.
12. Three targets, seven inputs
Question: Evaluate T(7,3).
Worked result: 3⁷−3·2⁷+3=2187−384+3=1806.
Reasoning check: The general formula scales without enumerating every assignment.
13. Three targets, eight inputs
Question: Evaluate T(8,3).
Worked result: 3⁸−3·2⁸+3=6561−768+3=5796.
Reasoning check: The labelled count differs sharply from an identical-object stars-and-bars calculation.
14. Four targets, four inputs
Question: Evaluate T(4,4).
Worked result: 4!=24.
Reasoning check: With equal finite sizes, a surjection is a permutation.
15. Four targets, five inputs
Question: Evaluate T(5,4).
Worked result: 4⁵−4·3⁵+6·2⁵−4=1024−972+192−4=240.
Reasoning check: Different missing-target intersections require alternating signs.
16. Four targets, six inputs
Question: Evaluate T(6,4).
Worked result: 4096−4·729+6·64−4=1560.
Reasoning check: The coefficients 4,6,4 count sets of one, two and three omitted targets.
17. Five targets, five inputs
Question: Evaluate T(5,5).
Worked result: 5!=120.
Reasoning check: Every target must be hit once when there are exactly as many inputs as targets.
18. Five targets, six inputs
Question: Evaluate T(6,5).
Worked result: There are 1800 surjections. One target receives two of six distinct inputs and the other four get one each: 5×C(6,2)×4!=1800.
Reasoning check: An occupancy classification can be simpler than inclusion–exclusion near n=k.
19. All functions, no onto requirement
Question: How many functions from four labelled students to three labelled teams exist?
Worked result: 3⁴=81 because each student chooses one of three outputs.
Reasoning check: Independent choices count assignments when empty teams are permitted.
20. Missing Red team
Question: Among those 81 functions, how many leave Red empty?
Worked result: 2⁴=16, since every student chooses only Blue or Green.
Reasoning check: An omitted-target event reduces the number of available outputs by one.
21. Missing two teams
Question: How many assignments omit both Red and Blue?
Worked result: Exactly one: every student joins Green.
Reasoning check: Overlapping omitted-target sets explain the inclusion–exclusion correction.
22. Nonempty three-team shape
Question: What group-size pattern must four students in three nonempty teams have?
Worked result: The occupancy pattern is 2,1,1 in some order.
Reasoning check: Total size four across three positive integers forces exactly one double occupancy.
23. Count 2,1,1 allocations
Question: How many labelled four-student, three-team allocations of size 2,1,1 exist?
Worked result: Choose the double team (3), its two members C(4,2)=6 and assign remaining singles in two orders, for 36.
Reasoning check: An alternative direct count independently checks the inclusion–exclusion result.
24. A five-student pattern
Question: What positive occupancy patterns exist for five students across three teams?
Worked result: Ignoring team order, the patterns are 3,1,1 and 2,2,1.
Reasoning check: Classify by integer partitions before counting labelled assignments.
25. Count the 3,1,1 pattern
Question: How many surjections of five students onto three labelled teams have occupancy 3,1,1?
Worked result: Choose triple team 3, choose its members C(5,3)=10 and assign singles 2 ways: 60.
Reasoning check: Fix the occupancy structure to avoid overlapping cases.
26. Count the 2,2,1 pattern
Question: How many five-student assignments have occupancy 2,2,1?
Worked result: Choose singleton team 3, its student 5, and two of the other four for a specified remaining team C(4,2)=6: total 90.
Reasoning check: The other pair is then determined, so do not divide again.
27. Check five into three
Question: Why does T(5,3)=150?
Worked result: The 3,1,1 pattern gives 60 and the 2,2,1 pattern gives 90; their sum is 150.
Reasoning check: A second counting method provides proof-level verification.
28. Six students shape 4,1,1
Question: Count assignments of six distinct students into labelled sizes 4,1,1.
Worked result: Choose the four-member team 3, its four members C(6,4)=15, then order two singles 2 ways: 90.
Reasoning check: Count each distinct team-size pattern without overlap.
29. Six students shape 3,2,1
Question: Count six students in labelled team sizes 3,2,1.
Worked result: Assign the three different sizes to the three teams in 3! ways and distribute students in 6!/(3!2!1!)=60 ways: total 360.
Reasoning check: Distinct group sizes make all six label assignments different.
30. Six students shape 2,2,2
Question: Count assignments with two students in each of three labelled teams.
Worked result: Use 6!/(2!2!2!)=90.
Reasoning check: A multinomial coefficient counts labelled groups with fixed sizes.
31. Check six into three
Question: Combine the three feasible patterns for six students and three nonempty teams.
Worked result: 90+360+90=540, matching T(6,3).
Reasoning check: All positive occupancy patterns have been exhausted.
32. One team cannot be empty
Question: What restriction distinguishes a surjection from an arbitrary function?
Worked result: Every codomain value must have at least one preimage.
Reasoning check: The condition concerns the image covering the full codomain.
33. Injection versus surjection
Question: Can a function from three inputs to two targets be injective?
Worked result: No, by pigeonhole. It can be surjective if both targets are reached.
Reasoning check: Different function properties have different cardinality constraints.
34. Equal size means bijection
Question: If a function from four inputs to four targets is onto, must it be one-to-one?
Worked result: Yes, all four targets must be used exactly once.
Reasoning check: On equal finite sets, surjectivity forces injectivity.
35. Onto probability for four and three
Question: Assuming uniform independent assignments, what is the chance all three teams are nonempty?
Worked result: 36/81=4/9.
Reasoning check: Divide favourable functions by total equally likely functions only when the model supports uniformity.
36. Onto probability for three and two
Question: Three inputs independently choose two targets uniformly. What is the probability both targets are used?
Worked result: 6/8=3/4.
Reasoning check: The numerator counts complete coverage.
37. Onto probability for four and two
Question: What is the probability both targets receive something for four uniform assignments?
Worked result: 14/16=7/8.
Reasoning check: The complement consists of two constant assignments.
38. Onto probability for five and three
Question: How likely is full occupancy under uniform assignment?
Worked result: 150/243=50/81.
Reasoning check: A probability of every box being occupied is not an expected occupied-box count.
39. Uniformity assumption
Question: Why would T(n,k)/k^n fail if some targets are favoured?
Worked result: The complete functions would no longer be equally likely, so count ratio would not equal probability.
Reasoning check: State the random-assignment distribution before using a combinatorial probability.
40. Expected occupied boxes
Question: Under n independent uniform placements into k boxes, what is the expected number occupied?
Worked result: k[1−(1−1/k)^n], by summing occupancy indicators.
Reasoning check: An expected count and the probability of complete occupancy are different quantities.
41. Identical objects
Question: How many ways to put eight identical objects into three labelled boxes, allowing empties?
Worked result: C(10,2)=45 by stars and bars.
Reasoning check: Do not use onto-function counts when individual objects are indistinguishable.
42. Identical objects and no empties
Question: How many positive count triples total eight?
Worked result: C(7,2)=21.
Reasoning check: Subtract one object per labelled box before applying stars and bars.
43. Distinct objects and no empties
Question: How many ways to put eight labelled objects into three labelled nonempty boxes?
Worked result: T(8,3)=5796.
Reasoning check: Object labels create many distinct functions with the same occupancy counts.
44. Unlabelled boxes
Question: How many partitions of four labelled objects into two nonempty unlabelled groups exist?
Worked result: T(4,2)/2!=14/2=7.
Reasoning check: Permuting nonempty target labels creates two labelled surjections for each unlabelled partition.
45. Unlabelled three groups
Question: How many partitions of four distinct objects into three nonempty unlabelled groups exist?
Worked result: T(4,3)/3!=36/6=6.
Reasoning check: The group of size two is determined by choosing its two members.
46. Stirling for five and three
Question: How many partitions of five distinct objects into three nonempty unlabelled groups?
Worked result: T(5,3)/3!=150/6=25.
Reasoning check: The label-dividing factor is justified because all blocks are nonempty and distinct.
47. Why labels divide by factorial
Question: Why is division by k! valid for onto functions to unlabelled groups?
Worked result: Every partition into k nonempty groups admits exactly k! distinct labellings of its blocks.
Reasoning check: The number of label assignments is uniform in this restricted setting.
48. A recurrence boundary
Question: What is T(n,1) for n≥1?
Worked result: Exactly one, because each input must choose the only target.
Reasoning check: Use this base condition when computing recurrence tables.
49. Another recurrence boundary
Question: What is T(n,n)?
Worked result: n!, since surjections with equal input and target sizes are bijections.
Reasoning check: Factorial counts supply a clean diagonal base.
50. The recurrence
Question: State a recurrence for the onto count T(n,k).
Worked result: T(n,k)=kT(n−1,k)+kT(n−1,k−1) for appropriate n,k.
Reasoning check: Split according to whether the last input’s target was already reached earlier.
51. Recurrence check 4,3
Question: Use the recurrence to obtain T(4,3).
Worked result: 3T(3,3)+3T(3,2)=3×6+3×6=36.
Reasoning check: Different derivations should produce identical counts.
52. Recurrence check 5,3
Question: Use the recurrence to obtain T(5,3).
Worked result: 3T(4,3)+3T(4,2)=3×36+3×14=150.
Reasoning check: Correct base cases and subproblem counts matter.
53. A zero-surjection case
Question: What is T(3,4)?
Worked result: Zero because three inputs cannot reach four distinct targets.
Reasoning check: Apply the cardinality obstruction before any formula.
54. A mistaken division
Question: Can T(n,k) always be divided by k! if targets may be empty?
Worked result: Not to count unlabelled allocations straightforwardly; empty blocks create label symmetries of differing sizes.
Reasoning check: The nonempty restriction is essential to the simple k! correspondence.
55. Mark the empty-target events
Question: What does E_j represent in inclusion–exclusion?
Worked result: The set of functions omitting one specified codomain target j.
Reasoning check: A meaningful event definition turns an alternating formula into a proof.
56. An intersection of omissions
Question: What happens if two distinct targets are forbidden?
Worked result: Only k−2 outputs remain, yielding (k−2)^n functions from an n-element domain.
Reasoning check: The size of an intersection depends on how many targets are omitted.
57. Choose which are absent
Question: Where does C(k,j) arise?
Worked result: It chooses the j distinct codomain targets that are missing.
Reasoning check: The binomial coefficient counts sets of omitted targets, not assignments of inputs.
58. A negative-term misconception
Question: Does a negative term in inclusion–exclusion mean a negative number of assignments?
Worked result: No. It is a correction for objects counted multiple times in earlier terms.
Reasoning check: The final total remains a nonnegative count.
59. One solution and full proof
Question: Is a numerical count such as 36 enough to prove the general formula?
Worked result: No. The general inclusion–exclusion argument explains every n and k with their domains.
Reasoning check: A small case checks arithmetic but does not establish universal validity.
60. Counting all functions
Question: How many functions from five labelled inputs to three labelled targets exist?
Worked result: 3⁵=243, without onto restriction.
Reasoning check: Each input has three output choices, producing independent choices in the combinatorial count.
61. Source and target roles
Question: Does swapping n and k preserve T(n,k)?
Worked result: No. T(4,3)=36 while T(3,4)=0.
Reasoning check: The function direction and onto condition matter.
A focused seven-session JC2 tutorial plan
Session one: distinguish labelled and unlabelled objects, labelled and unlabelled boxes, and whether any empty group is permitted. Have the student translate four practical arrangements into precise counting models before attempting arithmetic.
Session two: count all functions from a finite domain and identify the sets of functions that omit each target. Derive the first two terms of inclusion–exclusion and use a small case to show why intersections must be restored.
Session three: derive the full alternating sum for T(n,k) with correct binomial coefficients. Explain why a j-fold omission leaves k−j output choices for each input. Check the boundary n<k and n=k.
Session four: solve four students into three labelled nonempty teams in two ways. Compare the inclusion–exclusion answer 36 with the direct 2,1,1 occupancy count and identify why the two arguments enumerate the same assignments.
Session five: investigate five and six inputs into three targets. Classify positive occupancy patterns and compare the totals 150 and 540 with the alternating-sum formula. Keep team labels and student labels consistent throughout.
Session six: derive the recurrence T(n,k)=kT(n−1,k)+kT(n−1,k−1) by classifying the last input’s target. Use it to calculate T(4,3) and T(5,3) from smaller values.
Session seven: introduce probability of full occupancy under independent uniform assignment and contrast it with expected number occupied. Ask the learner to state exactly where the probability model is used.
At home, ask whether changing two students’ identities creates a new allocation, whether all teams must be filled, and what the total pool of functions includes. Those questions uncover the modelling choice underlying the formula.
The immutable eduKateSG Mathematics reference describes a three-student Secondary 1 tutorial format near Sixth Avenue MRT; it is not confirmation of a current JC2 H3 class. Contact eduKateSG to enquire about advanced Mathematics support.
Frequently asked questions
What is a surjective function?
A function whose image equals its codomain. Every codomain target receives at least one domain element.
How many onto functions are there from n labelled inputs to k labelled targets?
For positive integers n,k, the inclusion–exclusion formula Σ_{j=0}^k (−1)^j C(k,j)(k−j)^n counts them.
Why are there no onto functions when n<k?
Fewer than k input objects cannot reach k distinct codomain targets. This is a direct counting obstruction.
How do surjections differ from stars and bars?
Surjection counting typically treats domain objects as distinct. Stars and bars counts allocations of indistinguishable objects to labelled boxes by occupancy numbers.
What if the targets are unlabelled?
With k nonempty groups, divide the onto-function count by k! to count partitions of n distinct objects into k unlabelled blocks.
Is independence needed for the onto count?
No. Counting functions is combinatorial. Independence and uniformity matter only when converting counts to probabilities by dividing by k^n.
What is the simplest boundary case?
When n=k, an onto function is a bijection, so the number is k!. When k=1 and n≥1, there is one onto function.
Is this separately named as an H3 9820 topic?
The official syllabus names the bijection and inclusion–exclusion principles. Counting surjections is an original enrichment application of those principles, not a separately listed compulsory topic.
Why is a recurrence useful?
It classifies how the final input interacts with earlier inputs, giving a second proof of the count and an efficient way to calculate small values.
How should a JC2 tutor diagnose a counting mistake?
Ask which objects are distinguishable, whether boxes are labelled, which must be nonempty and whether the student is counting functions, partitions or occupancy patterns.
Official reference and related counting guides
The 2027 H3 Mathematics syllabus 9820 specifies the bijection and inclusion–exclusion principles, along with combinatorial proof. This guide uses onto functions as original extension problems and does not claim an additional named examination chapter.
For related techniques, consult bijection and stars and bars, inclusion–exclusion, and indicator variables and expectation. The essential skill is modelling the distinct counted objects accurately.
Four questions that make an onto-count proof reliable
What are the objects? If four students are distinct, switching student A and student B can change an assignment. Identical counters cannot be distinguished in that way. Decide this before choosing between functions and stars-and-bars patterns. Likewise, giving labels to teams changes whether permuting the group names produces another outcome.
What is forbidden? The onto condition forbids empty targets. Construct a missing-target event for each target label. The intersections of these events are not incidental; they explain the alternating corrections in inclusion–exclusion. A student who writes an alternating sum without identifying its objects is memorising the result rather than proving it.
Have all cases been counted once? In a direct occupancy proof, specify an exact size pattern such as 2,1,1, then count assignments under that pattern. If different patterns are disjoint and exhaustive, their counts can safely be added. For a recurrence, state why the final input either uses an already occupied target or is uniquely responsible for a previously empty one.
What does the result mean? A surjection count is a number of functions. It becomes a probability only after a distribution over functions is supplied. In a uniform independent assignment model, divide by k to the power n; in a nonuniform model, count ratios do not automatically give probabilities. This distinction connects proof, combinatorics and responsible mathematical modelling.