Counting functions between finite sets
With |A| = m and |B| = n there are nᵐ functions A → B, since each of the m inputs independently picks one of n outputs. Injections number n(n−1)…(n−m+1), the falling factorial, because each input must avoid the previously used outputs. Bijections exist only when m = n, and then there are n! of them.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- All functions — independent choicesnᵐ. Note the exponent is the size of the DOMAIN, which is the opposite of most people’s first guess.
- Injections — falling factorialn·(n−1)···(n−m+1), which is 0 when m > n by pigeonhole.
- Bijections — factorialn! when m = n, and none otherwise.
- Surjections — inclusion–exclusionΣ_{k} (−1)^k C(n,k)(n−k)^m, equivalently n!·S(m,n) with Stirling numbers of the second kind.
Worked example
With |A| = 3 and |B| = 4, count the functions A → B, the injections, and the surjections.
- Functions: 4³ = 64.
- Injections: 4 · 3 · 2 = 24.
- Surjections A → B need every element of B hit, but |A| = 3 < 4 = |B|.
- By pigeonhole three inputs cannot cover four outputs.
Answer. 64 functions, 24 injections, and 0 surjections.
Where marks get dropped
These are the specific errors that cost credit on counting functions between finite sets questions — QED's rubric penalises each of them separately.
- Writing mⁿ instead of nᵐ. The base is the codomain size and the exponent is the domain size.
- Expecting a simple product formula for surjections. They need inclusion–exclusion or Stirling numbers.
- Forgetting that injections require |A| ≤ |B| and surjections require |A| ≥ |B|.
Practise this until it is automatic
Unlimited fresh questions
QED generates new counting functions between finite sets problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Functions mastery is tracked so you know when this is exam-ready.
Counting functions between finite sets — frequently asked questions
Why is it nᵐ and not mⁿ?
Each of the m domain elements independently chooses one of n images, giving n × n × … × n with m factors. Thinking of a function as a length-m string over an n-letter alphabet makes it obvious.
How many surjections from a 4-set onto a 3-set?
36 — from 3!·S(4,3) = 6·6. The inclusion–exclusion form 3⁴ − 3·2⁴ + 3·1⁴ = 81 − 48 + 3 gives the same.
What if the sets are infinite?
Counting is replaced by cardinal arithmetic. The set of functions ℕ → {0,1} has cardinality 2^ℵ₀, the cardinality of ℝ.
The rest of Functions
Injective, surjective, bijective, composition, inverse. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Domain, codomain, image & preimage
- 2Injective, surjective & bijective
- 3Composition g∘f and its properties
- 4Inverse functions
- 5Counting functions between finite sets
- 6Images & preimages of unions and intersections
- 7Restriction, extension & piecewise definitions
- 8Pigeonhole consequences for injections
- 9Countability via a bijection with ℕ
- 10Well-definedness of a proposed function
- 11Monotone & strictly increasing functions
- 12Identity, constant & inclusion functions
- 13Partial functions, totality & undefinedness
Ready to make counting functions between finite sets exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →