Counting Functions

Context: FIT1058_MOC · counts how many functions of each type exist between finite sets · uses the product rule · linked to Injection, Surjection, Bijection

Quick Revision

• 🎯 Objective: count functions $f:A\to B$ by type ($|A|=m$, $|B|=n$) ➔ all / injective / bijective.
• 📦 Core Components: all $=n^m$ ➔ injections $=\frac{n!}{(n-m)!}$ ➔ bijections $=n!$.
• ⚡ Key Constraint: injections vanish if $m>n$ (pigeonhole); surjections need inclusion–exclusion.

📝 Core

1. The Counts

• All functions ➔ $n^m$ (each of $m$ inputs picks any of $n$ outputs independently).
• Injections ➔ $\frac{n!}{(n-m)!}=n(n-1)\cdots (n-m+1)$ (choices shrink; $0$ if $m>n$).
• Bijections ➔ $n!$ (needs $m=n$; permutations of the set).

2. Why the Formulas

• Product rule ➔ independent choices multiply ⟹ $n^m$.
• Shrinking choices ➔ each used value unavailable ⟹ falling product.
• Pigeonhole ➔ $m>n$ forces a collision ⟹ no injection.

3. What’s Deferred

• Surjections ➔ inclusion–exclusion / Stirling numbers of the second kind (not a simple product).

Key identities:

$\#\{f:A\to B\}=n^m,\#\text{injections}=\frac{n!}{(n-m)!},\#\text{bijections}=n!(m=n)$

⚖️ Core Decision Matrix

Type	Count	Reason
all functions	$n^m$	$n$ choices, $m$ times
injections	$\frac{n!}{(n-m)!}$	shrinking choices; $0$ if $m>n$
bijections ($m=n$)	$n!$	permutations
surjections	inclusion–exclusion	not a plain product

When It Flips: every bijection is an injection with $m=n$: $\frac{n!}{0!}=n!$ (consistent). Relations ($2^{mn}$, n-ary Relation) vastly outnumber functions ($n^m$) because they drop single-valuedness.

📊 Exam Execution Trace

Manual Execution Trace

$|A|=2$, $|B|=3$:

Step / State	Type	Formula	Value
0 (Init)	—	—	—
1	all	$3^2$	9
2	injections	$3!/1!$	6
3	bijections ($m=n=3$)	$3!$	6

⚠️ Common Mistakes

• 💡 Injections keep order, subsets don’t ➔ $\frac{n!}{(n-m)!}$ is the ordered selection; dividing by $m!$ gives $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ (Binomial Coefficient). Injections vanish when $m>n$.

🧠 Active Recall

Derive the number of functions and injections from a size- $m$ to a size-$n$ set.

• Hint: Independent vs shrinking choices.

Answer

• Short answer: Functions $n^m$; injections $n(n-1)\cdots (n-m+1)=\frac{n!}{(n-m)!}$.
• Why: Pigeonhole ➔ $m>n$ makes a factor $\le 0$, count $0$.

Why is the number of bijections on an $n$-set $n!$, and what are they called?

• Hint: $m=n$ injection count.

Answer

• Short answer: $\frac{n!}{0!}=n!$; these are the permutations.
• Why: Falling product ➔ $n,n-1,\dots ,1$ distinct image choices.