Find Number of Surjections

🎥 Video Explanation

---

📝 Question

Let \(A=\{1,2,\dots,n\}\) and \(B=\{a,b\}\).

Find number of surjections from \(A\) to \(B\).

• (a) \(nP_2\)
• (b) \(2^n – 2\)
• (c) \(2^n – 1\)
• (d) \(nC_2\)

---

✅ Solution

🔹 Step 1: Total Functions

Each element of \(A\) can map to either \(a\) or \(b\):

\[ \text{Total functions} = 2^n \] —

🔹 Step 2: Remove Non-Onto Cases

Not onto means:

• All elements map to \(a\)
• All elements map to \(b\)

Number of such functions = 2

—

🔹 Step 3: Surjections

\[ \text{Onto functions} = 2^n – 2 \] —

🔹 Final Answer

\[ \boxed{\text{Option (b)}} \]