Surjections from [n] to [k]: functions where every element in [k] is hit. Count by inclusion-exclusion: Σ(-1)^i·C(k,i)·(k-i)^n for i=0..k. Equals k!·S₂(n,k) where S₂ is Stirling 2nd kind. For k=n: = n! (bijections = derangements × 0 + permutations).
How to Use
Enter n (domain) and k (codomain):
- Count: Number of surjections
- Steps: Each inclusion-exclusion term
- Stirling: S₂(n,k) connection
Inclusion-Exclusion
Total functions: k^n. Subtract those missing ≥1 element. Add back those missing ≥2. Etc. Term i: (-1)^i · C(k,i) · (k-i)^n = # functions missing at least i specific targets.
Stirling Connection
S₂(n,k) = surjections / k! = # ways to partition [n] into k non-empty subsets. The surjection count assigns labels (k! orderings) to each partition.
Step-by-Step Instructions
- 1Enter domain size n.
- 2Enter codomain size k.
- 3Compute surjections.
- 4View IE steps.
- 5Check Stirling.