• Advanced
  • About 16 min
  • 5 practice questions

Counting onto functions and functions with conditions

Count onto functions between finite sets by inclusion-exclusion or by grouping, and count functions and bijections that must satisfy extra conditions such as fixed values or increasing order.

If something looks wrong, please tell us.

The Foundation and Practice courses counted all functions (n^m) and one-one functions (n × (n − 1) × ... for m factors) from a set of m elements to a set of n elements. Harder questions ask for onto functions, or put conditions on the functions: a value that is fixed, a value that is forbidden, or an order that must be kept. These counts cannot be done by a single multiplication, but each one has a dependable method. This lesson sets out the methods and shows how to check an answer by a second route.

Onto functions by subtracting the failures

A function from A to B is onto when every element of B is used at least once. Counting these directly is awkward, so count all functions and remove the ones that miss some element. Suppose |A| = m and |B| = n. The functions that miss one named element of B are the functions into the other n − 1 elements, and there are (n − 1)^m of them. There are C(n, 1) ways to name that element. But a function that misses two elements has now been removed twice, so it must be added back, and so on. This is inclusion-exclusion, and it gives the formula below.

Onto functions from an m-element set to an n-element set: n^m − C(n, 1)(n − 1)^m + C(n, 2)(n − 2)^m − C(n, 3)(n − 3)^m + ... (stop at the term with (n − n)). If m < n there are none; if m = n they are the n! bijections.

— Rule to remember

For n = 2 the formula is simply 2^m − 2: every function except the two constant ones is onto. For n = 3 it is 3^m − 3 × 2^m + 3.

Worked example 1: onto functions from 5 elements to 3

Let A = {1, 2, 3, 4, 5} and B = {a, b, c}. All functions: 3^5 = 243. Functions missing a named element: 2^5 = 32 each, and there are 3 choices of the missing element, so subtract 3 × 32 = 96. Functions missing two named elements are constant, 1^5 = 1 each, with C(3, 2) = 3 choices, so add back 3. The count is 243 − 96 + 3 = 150.

Check by grouping. An onto function splits A into three non-empty groups, one for each image. The group sizes must be 3, 1, 1 or 2, 2, 1. Sizes 3, 1, 1: choose the group of three in C(5, 3) = 10 ways, and the other two elements are singletons. Sizes 2, 2, 1: choose the singleton in 5 ways and split the other four into two pairs in 3 ways, giving 15. That is 25 groupings, and each can be matched with a, b, c in 3! = 6 ways: 25 × 6 = 150. Both routes agree.

Worked example 2: five elements onto four

From 5 elements onto 4, exactly one image is used twice and the others once. Choose the pair of elements that share an image: C(5, 2) = 10. That leaves four groups to match with four images in 4! = 24 ways, so there are 240 onto functions. The formula gives 4^5 − 4 × 3^5 + 6 × 2^5 − 4 × 1^5 = 1024 − 972 + 192 − 4 = 240. A question that asks for functions that are NOT onto is then 1024 − 240 = 784.

Fixed and forbidden values

A condition on one element is handled first, then the rest are counted freely. For functions from {1, 2, 3, 4} to itself with f(1) ≠ 1, the element 1 has 3 choices and each of the others has 4, giving 3 × 4 × 4 × 4 = 192. For bijections from {1, 2, 3, 4} to {a, b, c, d} with f(1) ≠ a, count all 4! = 24 bijections and subtract those with f(1) = a, which are the 3! = 6 bijections of the remaining elements: 24 − 6 = 18. Subtracting the forbidden case is usually safer than building the count directly.

Symmetry also helps. Of the 150 onto functions from {1, 2, 3, 4, 5} to {a, b, c}, the value f(1) is a in exactly one third of them, because swapping the names of the images turns one kind into another. So 50 onto functions have f(1) = a.

Strictly increasing functions

Let A = {1, 2, 3} and B = {1, 2, 3, 4, 5, 6}. A strictly increasing function f (f(1) < f(2) < f(3)) is fixed completely once you know which three values it takes, because the values must be listed in increasing order. So the count equals the number of 3-element subsets of B: C(6, 3) = 20. In general there are C(n, m) strictly increasing functions from {1, ..., m} to {1, ..., n}, which is the number of one-one functions divided by m!.

Counts to recognise at once
Kind of function, |A| = m, |B| = nCountExample m = 3, n = 5
All functionsn^m125
One-onen(n − 1)...(n − m + 1)60
Strictly increasingC(n, m)10
Onto (m < n)00

Key takeaways

Count onto functions by inclusion-exclusion and check by grouping the elements of A. Remove a forbidden value by subtracting the functions that use it. Use symmetry between the images when one value is fixed. An increasing function is a choice of a subset, so its count is a combination.

Check your understanding

  1. 1. How many onto functions are there from {1, 2, 3, 4, 5} to {a, b}?

    1. 30
    2. 32
    3. 10
    4. 25
    Show answer

    Answer: A. All functions: 2^5 = 32. Only the two constant functions miss an image, so 32 − 2 = 30 are onto.

  2. 2. How many onto functions are there from a set with 4 elements to a set with 3 elements?

    1. 36
    2. 81
    3. 24
    4. 48
    Show answer

    Answer: A. 3^4 − 3 × 2^4 + 3 × 1 = 81 − 48 + 3 = 36. Check: choose the pair sharing an image in C(4, 2) = 6 ways, then match three groups with three images in 3! = 6 ways: 36.

  3. 3. How many strictly increasing functions are there from {1, 2, 3} to {1, 2, 3, 4, 5, 6}?

    1. 120
    2. 216
    3. 60
    4. 20
    Show answer

    Answer: D. Each increasing function is fixed by its set of three values, so the count is C(6, 3) = 20. (120 counts all one-one functions.)

  4. 4. How many one-one functions from {1, 2, 3} to {1, 2, 3, 4, 5} have f(1) = 2?

    1. 25
    2. 12
    3. 60
    4. 20
    Show answer

    Answer: B. f(1) is fixed. f(2) can be any of the 4 remaining values and f(3) any of the 3 left: 4 × 3 = 12.

  5. 5. A has 5 elements and B has 4. How many functions from A to B are NOT onto?

    1. 240
    2. 1024
    3. 880
    4. 784
    Show answer

    Answer: D. All functions: 4^5 = 1024. Onto functions: C(5, 2) × 4! = 10 × 24 = 240. Not onto: 1024 − 240 = 784.

Privacy · Terms · Refunds · Delivery