Course contentsShow
← Mathematics
Lesson 2625 of 3,12152. CombinatoricsFree lesson

Counting Surjective Functions

Using inclusion-exclusion to count onto functions between finite sets.

Counting Surjective Functions

What you'll learn: How to use the inclusion-exclusion principle to count the number of surjective (onto) functions from one finite set to another.

The Challenge

You've learned what surjective functions are—functions where every element in the codomain is "hit" by at least one element from the domain. But how many such functions exist from a set of size n to a set of size k?

The total number of functions from an n-element set to a k-element set is k^n (each of n elements has k choices). But counting only the surjective ones requires eliminating those functions that "miss" at least one codomain element.

Using Inclusion-Exclusion

This is a perfect job for the inclusion-exclusion principle! Let Aᵢ be the set of functions that do not map onto the i-th element of the codomain.

We want functions in none of these bad sets—that is, onto functions equal:

Total functions - |A₁ ∪ A₂ ∪ ... ∪ A_k|

By inclusion-exclusion:

  • |Aᵢ| counts functions avoiding one specific element: (k-1)^n
  • |Aᵢ ∩ A_j| counts functions avoiding two elements: (k-2)^n
  • And so on...

The formula becomes:

Number of surjections = Σ (-1)^i · C(k,i) · (k-i)^n for i from 0 to k

This equals: k^n - C(k,1)(k-1)^n + C(k,2)(k-2)^n - ...

Example

Functions from {1,2,3} onto {A,B}: 2³ - C(2,1)·1³ = 8 - 2·1 = 6 surjective functions

Key Takeaway: The number of surjective functions is computed by inclusion-exclusion: start with all functions, then alternately subtract and add terms that count functions missing one or more codomain elements.