Let $A = \{1, 2, 3, \ldots n\}$ and $B = \{a, b\}$. Then the number of surjections from $A$ into $B$ is (A) $^{n}P_2$ (B) $2^n - 2$ (C) $2^n - 1$ (D) none of these

Let A = \1, 2, 3, … n\ and B = \a, b\. Then the nu – 2nd PUC Mathematics

NCERT Exemplar · Q25

A = \{1, 2, 3, \ldots n\}

Karnataka PUCMCQ· 1mImportance★★★★★

83% · 86/104 Questions

🔒 Locked · start free trial →

You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.

Start your 14-day free trial to unlock the full solution →

Concept understanding — Inclusion Exclusion Principle

The Inclusion–Exclusion Principle

Thirty students play cricket and twenty-five play football — so does "cricket or football" total $55$ ? Not if some play both. If ten play both, they have been counted twice, so the real total is $30 + 25 - 10 = 45$ . That single correction is the whole principle: add everything, then subtract what you double-counted.

Why "Inclusion" and "Exclusion"

Include every set by adding its size.
Exclude the overlaps counted more than once by subtracting the intersections.

For three or more sets the signs keep alternating, because each correction slightly over-corrects and must itself be fixed.

The General Statement

For finite sets $A_1, A_2, \dots, A_n$ ,

\left| \bigcup_{i=1}^n A_i \right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}\,|A_1 \cap \cdots \cap A_n|.

Add all singles, subtract all pairwise intersections, add all triples, and so on — the sign alternates, starting with $+$ .

Why It Works

An element lying in exactly $m$ of the sets is counted $\binom{m}{1}$ times among the singles, subtracted $\binom{m}{2}$ times among the pairs, added $\binom{m}{3}$ times among the triples, and so on. Its net count is

\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots + (-1)^{m+1}\binom{m}{m} = 1,

using $(1-1)^m = 0$ from the binomial theorem. So every element is counted exactly once.

A Three-Set Example

Of $100$ students: $40$ take Physics, $30$ Chemistry, $25$ Biology; $15$ take P and C, $10$ P and B, $8$ C and B; $5$ take all three.

|P \cup C \cup B| = (40+30+25) - (15+10+8) + 5 = 95 - 33 + 5 = 67.

So $67$ take at least one subject and $33$ take none. …

Start your 14-day free trial to unlock the full solution →

The number of surjections from an $n$ -element set onto a 2-element set is found by counting all functions and subtracting the two constant functions. The answer is $2^n - 2$ , which corresponds to option (B).

A surjection (onto function) from set $A$ to set $B$ means every element of $B$ must have at least one preimage in $A$ . Here $B$ has exactly two elements: $a$ and $b$ . So we need every function from $A$ to $B$ where both $a$ and $b$ appear in the range at least once.

The total number of functions from $A$ to $B$ is $2^n$ , because each of the $n$ elements in $A$ can independently map to either $a$ or $b$ .

Among these, the functions that are not surjective are exactly those that miss at least one element of $B$ . Since $B$ has only two elements, a function misses $a$ if it maps every element of $A$ to $b$ — that's exactly one function (the constant function $f(x)=b$ ). Similarly, a function misses $b$ if it maps everything to $a$ — that's one function. There is no function that misses both $a$ and $b$ simultaneously (that would require mapping to nothing), so these two are the only non-surjective functions.

Thus the number of surjections is:

$\text{Total functions} - \text{Functions that miss } a - \text{Functions that miss } b = 2^n - 1 - 1 = 2^n - 2.$ …

Start your 14-day free trial to unlock the full solution →

Same / Similar Concept — real previous-year questions on the same or a closely similar concept, not this exact question.

KCET 2024Set A-11 markMCQ
$m$
›Reveal solutionSolution

Use $\#\text{subsets}=2^k$ , form $2^m-2^n=56$ , and factor out $2^n$ so the odd factor 7 forces $2^{m-n}-1=7$ .

Step 1 — The concept: number of subsets.

For a finite set with $k$ elements, each element is either in or out of a subset, so the power set has
$n(P(S))=2^{k}$
elements. This is why the problem is really about powers of 2.

Step 2 — Translate the condition.

First set has $m$ elements, second has $n$ :
$2^{m}-2^{n}=56$
Step 3 — Factor out the smaller power of 2.

Since $m>n$ (the first set has more subsets),
$2^{n}\left(2^{\,m-n}-1\right)=56$
Step 4 — Match the parity.

Write $56=2^{3}\times 7$ . The bracket $\left(2^{m-n}-1\right)$ is odd (a power of 2 minus 1), so it must absorb the whole odd part, and $2^n$ must absorb the whole power-of-2 part: …
Start your 14-day free trial to see the full solution →
KCET 2022Set C-41 markMCQ
$A = \{1, 2, 3, \ldots 10\}$
›Reveal solutionSolution

Subsets containing only odd numbers are precisely the subsets of the odd-element set $\{1,3,5,7,9\}$ ; there are $2^5=32$ of these, and dropping the empty set (which contains no odd number to speak of) gives 31.

Step 1 — Isolate the odd elements.
$A=\{1,2,3,4,5,6,7,8,9,10\},\qquad A_{\text{odd}}=\{1,3,5,7,9\},\quad |A_{\text{odd}}|=5.$
Step 2 — Why the count is a power of two.

A subset of $A$ whose elements are all odd cannot contain any of $2,4,6,8,10$ . So it is completely determined by an independent yes/no choice for each of the 5 odd elements. That is the standard result: a set with $n$ elements has $2^n$ subsets.
$\text{number of subsets of } A_{\text{odd}} = 2^{5}=32.$
Step 3 — Remove the empty set. …
Start your 14-day free trial to see the full solution →
KCET 2020Set A-11 markMCQ
$P(n) : 2^n < n!$
›Reveal solutionSolution
The inequality $2^n < n!$ fails for small $n$ and first holds at $n = 4$ , because $2^4 = 16$ while $4! = 24$ , and once true it stays true for all larger $n$ by induction.

The idea is simple: factorials grow much faster than exponentials once $n$ is large enough. For small $n$ , we just test directly. The question asks for the smallest positive integer where $2^n < n!$ holds — so we check $n = 1, 2, 3, \dots$ until we find the first success.

Watch out

A common mistake is to assume $2^n < n!$ is true for all $n \ge 4$ without checking $n = 4$ itself. Always test the candidate value.

Test $n = 1$ : $2^1 = 2$ , $1! = 1$ . Here $2 < 1$ is false. So $P(1)$ is false.

Test $n = 2$ : $2^2 = 4$ , $2! = 2$ . $4 < 2$ is false. So $P(2)$ is false.

Test $n = 3$ : $2^3 = 8$ , $3! = 6$ . $8 < 6$ is false. So $P(3)$ is false.

Test $n = 4$ : $2^4 = 16$ , $4! = 24$ . $16 < 24$ is true. So $P(4)$ is true. …
Start your 14-day free trial to see the full solution →
KCET 2021Set A-11 markMCQ
$Q. In a certain town 65% families own cellphones, 15000 families own scooter and 15% families own both. Taking into consideration that the families own at least one of the two, the total number of families in the town is (A) 20000 (B) 30000 (C) 40000 (D) 50000$
›Reveal solutionSolution
Use the principle of inclusion-exclusion for two sets: total families = families with cellphones + families with scooters – families with both. Given that every family owns at least one, the union is 100%. Solving gives total = 30,000.

Concept & Intuition

This is a classic set problem disguised as a word problem. We have two groups: families that own cellphones (set C) and families that own scooters (set S). The phrase "families own at least one of the two" tells us that the union of these two sets is the entire town — no family is left out. So the union is 100% of the families.

The trick is that the percentages given (65% cellphones, 15% both) are percentages of the total number of families, which we don't know yet. The 15,000 scooter-owning families is an absolute number. We need to connect the percentages to the absolute count using the inclusion-exclusion formula.
$|A \cup B| = |A| + |B| - |A \cap B|$
Here, $|A \cup B|$ is the total number of families (since every family owns at least one). Let the total be $T$ .

Step-by-step solution

Define variables and translate given data

Let $T$ = total number of families in the town.

Families with cellphones: $65\%$ of $T$ = $0.65T$

Families with scooters: 15,000 (absolute number)

Families with both: $15\%$ of $T$ = $0.15T$

Families with at least one: $T$ (given)

Apply inclusion-exclusion

The union of cellphone-owners and scooter-owners equals the whole town:

$T = (0.65T) + 15000 - (0.15T)$

Simplify the equation Combine the $T$ terms on the right: …
Start your 14-day free trial to see the full solution →
CA Foundation 2026Set may-20261 markMCQ
$Q. In a class, 50 students have expressed that they like Mathematics, while 66 students like Accountancy. Among these, 36 students like both Mathematics and Accountancy. Based on this information, determine how many students in the class like either Mathematics or Accountancy? (A) 14 (B) 20 (C) 52 (D) 80$
›Reveal solutionSolution

Union of two sets: $n(M\cup A) = n(M)+n(A)-n(M\cap A) = 50+66-36 = 80$ .

Step 1 — Inclusion–exclusion principle

Adding the two group sizes double-counts the students in both, so subtract the overlap once:
$n(M \cup A) = n(M) + n(A) - n(M \cap A)$
Step 2 — Substitute

$n(M)=50$ (Mathematics), $n(A)=66$ (Accountancy), $n(M\cap A)=36$ (both):
$n(M \cup A) = 50 + 66 - 36 = 80$
Why the other options are wrong: (A) 14 and (B) 20 are the “only one subject” counts ( $50-36=14$ , $66-36=30$ region pieces); (C) 52 forgets to subtract the overlap fully; only 80 is the full union. …
Start your 14-day free trial to see the full solution →

←Previous questionQ24 — If the set A contains 5 elements and the set B contains 6 elements, th…→Next questionQ26 — Let f : mathbbR → mathbbR be defined by f(x) = (1)/(x), ∀ x ∈ mathbbR.…

Q.Let $A = \{1, 2, 3, \ldots n\}$ and $B = \{a, b\}$ . Then the number of surjections from $A$ into $B$ is
(A) $^{n}P_2$
(B) $2^n - 2$
(C) $2^n - 1$
(D) none of these

Concept understanding — Inclusion Exclusion Principle

The Inclusion–Exclusion Principle

Why "Inclusion" and "Exclusion"

The General Statement

Why It Works

A Three-Set Example

Method: Counting Onto (Surjective) Functions

Steps

Common Mistakes

Step 1 — Inclusion–exclusion principle

Step 2 — Substitute

Q.Let A={1,2,3,…n}A = \{1, 2, 3, \ldots n\}A={1,2,3,…n} and B={a,b}B = \{a, b\}B={a,b}. Then the number of surjections from AAA into BBB is (A) nP2^{n}P_2nP2​ (B) 2n−22^n - 22n−2 (C) 2n−12^n - 12n−1 (D) none of these

🎓Unlock everything free for 14 days

Q.Let $A = \{1, 2, 3, \ldots n\}$ and $B = \{a, b\}$ . Then the number of surjections from $A$ into $B$ is
(A) $^{n}P_2$
(B) $2^n - 2$
(C) $2^n - 1$
(D) none of these

Unlock everything free for 14 days