On this page
A has 3 elements, B has 2: how many functions are there, how many are one-one, and how many are onto? We build the three formulas, then check every number by listing all eight functions.
Why are there nᵐ functions from A to B?
A function from A to B gives every element of A exactly one image in B. Images may repeat, and some elements of B may go unused.
So build the function one element at a time. The first element of A has n possible images; the second also has n, whatever the first chose. With m elements, the multiplication principle gives n × n × … × n = nᵐ.
The number of functions from an m-element set to an n-element set is nᵐ, the first entry in the twelvefold way, the standard table of counting problems (it uses different letters for the same result).
Relations are a different count, since a relation is any subset of A × B; see our post on counting relations from A to B.
How many one-one functions are there from A to B?
A one-one (injective) function never sends two elements of A to the same image. Now the choices shrink: the first element has n images available, the second n − 1, the third n − 2, and so on for m steps.
The number of one-one functions from an m-element set to an n-element set is the falling factorial n(n − 1)(n − 2)…(n − m + 1), as listed in the twelvefold way. When m ≤ n this equals n!/(n − m)!, the same as ⁿPₘ. When m > n one factor is zero, so there are none: three elements cannot have different images inside a set of two.
How do you count onto functions for small sets?
An onto (surjective) function uses every element of B as an image at least once. Start with all nᵐ functions and remove those that miss at least one element of B, using inclusion–exclusion for the overlaps:
Number of onto functions = nᵐ − C(n, 1)(n − 1)ᵐ + C(n, 2)(n − 2)ᵐ − …
The number of onto functions from an m-element set to an n-element set is n! × S(m, n), where S(m, n) is a Stirling number of the second kind: the number of ways to split m objects into n non-empty groups. If inclusion–exclusion feels rusty, our three-set Venn diagram walkthrough rebuilds it.
For small B, it shrinks to:
B has 2 elements: onto functions = 2ᵐ − 2
B has 3 elements: onto functions = 3ᵐ − 3 × 2ᵐ + 3
A smaller than B: zero, since m elements cannot cover n images
Check the 3-element rule with m = 3: 27 − 24 + 3 = 6, which is 3!. When the sets are the same size, onto and one-one mean the same thing.
Worked example: functions from a 3-element set to a 2-element set
Take A = {1, 2, 3} and B = {a, b}. Write each function as the list of images f(1), f(2), f(3).
All functions: each of 1, 2 and 3 picks a or b, so 2³ = 8. They are aaa, aab, aba, abb, baa, bab, bba and bbb.
One-one: 2 × 1 × 0 = 0. Three elements and two images means some image must repeat.
Onto: 2³ − 2 = 6. Only aaa and bbb miss an element of B.
Stirling check: S(3, 2) = 3, the splits {1}{2, 3}, {2}{1, 3} and {3}{1, 2}, matching the table on the Stirling numbers page. Then 2! × 3 = 6, as in step 3.
Direction matters. From B to A there are 3² = 9 functions, 3 × 2 = 6 one-one, and 0 onto, because two elements cannot cover three images.
Where do students lose marks on this?
Writing mⁿ instead of nᵐ.
Counting onto functions as nᵐ − n for every B. That removes only the constant functions, which is enough when B has 2 elements; from 3 up, non-constant functions can miss part of B too.
Leaving an element of A without an image: every element of the domain needs exactly one.
For proofs that a map is one-one or onto, see our explainer on one-one and onto functions. For practice, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, so you can see where a count went wrong. If the gap is the idea of a function itself, the Fermi Concept Library gives each concept its own lesson and its place in the map.
Try one now: count the onto functions from a 5-element set to a 3-element set with the 3-element rule, then check your answer against 3! × S(5, 3).
