Easy Practice — Set 1

Quick Recap — Sets

• Operations: $A\cup B$ (all elements), $A\cap B$ (common), $A-B$ (in $A$ not $B$), $A'$ (complement in $U$).
• Counting: subsets of an $n$-set $=2^n$; $n(A\cup B)=n(A)+n(B)-n(A\cap B)$.
• De Morgan: $(A\cup B)'=A'\cap B'$ and $(A\cap B)'=A'\cup B'$.
• Cartesian product: $n(A\times B)=n(A)\,n(B)$.

Beyond-NCERT JEE Formulae

1. Onto (surjective) function count. The number of onto functions from an $n$-element set to an $m$-element set (with $m\le n$) is

$$\sum_{k=0}^{m}(-1)^k\,{}^{m}C_k\,(m-k)^n.$$

When to use: counting surjections, or distributing $n$ distinct objects into $m$ distinct non-empty boxes. [JEE Tip] For $m=2$ this collapses to $2^n-2$ (drop the two constant maps); for $m=3$ it is $3^n-3\cdot 2^n+3$.

2. Equivalence relations are counted by Bell numbers. The number of equivalence relations on an $n$-set equals the number of partitions of that set, the Bell number $B_n$, with $B_1,B_2,B_3,B_4,B_5=1,2,5,15,52$ and recurrence $B_{n+1}=\sum_{k=0}^{n}{}^{n}C_k\,B_k$. When to use: any "how many equivalence relations / partitions" question. [JEE Tip] Never a power of $2$ here; equivalence relations follow $B_n$, not $2^{(\cdots)}$.

3. Relation counts on an $n$-set. Of the $2^{n^2}$ relations on the set: reflexive $=2^{n^2-n}$ (the $n$ diagonal cells are forced in, the other $n^2-n$ cells free); symmetric $=2^{n(n+1)/2}$ (the $n$ diagonal cells and the $\dfrac{n(n-1)}{2}$ upper-triangle pairs are free); reflexive and symmetric together $=2^{n(n-1)/2}$ (only those $\dfrac{n(n-1)}{2}$ upper-triangle pairs stay free). When to use: "count the relations that are reflexive and/or symmetric" problems. [JEE Tip] Antisymmetric $=2^{n}\cdot 3^{n(n-1)/2}$; transitive has no neat closed form, so enumerate for small $n$.

4. Even-odd decomposition. On a domain symmetric about $0$, every function splits uniquely as

$$f(x)=\tfrac12\big[f(x)+f(-x)\big]+\tfrac12\big[f(x)-f(-x)\big],$$

the first bracket even and the second odd. When to use: extracting even/odd parts, or killing the odd part inside a symmetric definite integral. [JEE Tip] For $f(x)=e^{x}$ the two parts are exactly $\cosh x$ and $\sinh x$.

5. Standard functional-equation families (assuming the usual continuity). $f(x+y)=f(x)+f(y)\Rightarrow f(x)=cx$ with $c=f(1)$ (Cauchy additive). $f(xy)=f(x)+f(y)\Rightarrow f(x)=k\ln x$, and $f(1)=0$. $f(x+y)=f(x)\,f(y)\Rightarrow f(x)=a^{x}$ with $a=f(1)$. $f(x)\,f(1/x)=f(x)+f(1/x)\Rightarrow f(x)=1\pm x^{n}$ (its polynomial solutions). When to use: "$f$ satisfies this identity, find $f$" problems. [JEE Tip] Substitute $x=y=1$ (or $x=y=0$) first to fix the constant, then one small integer to pin the exponent or the slope.

Solved Examples — Beyond-NCERT Formulae

Example 1: Onto functions from a 5-set onto a 3-set. How many onto (surjective) functions $f:A\to B$ exist when $|A|=5$ and $|B|=3$?

Solution:

1. Formula: onto count $=\sum_{k=0}^{m}(-1)^k\,{}^{m}C_k\,(m-k)^n$; here $n=5$ and $m=3$.
2. Expand the four terms: ${}^{3}C_0\,3^5-{}^{3}C_1\,2^5+{}^{3}C_2\,1^5-{}^{3}C_3\,0^5$.
3. Evaluate: $1\times 243-3\times 32+3\times 1-0=243-96+3$.
4. Hence the total is $150$.

Takeaway: surjection counts come straight from inclusion-exclusion; subtract the maps that miss one target, then add back those missing two.

Example 2: Onto functions onto a 2-set (special case). How many onto functions are there from a 6-element set to the 2-element set $\{0,1\}$?

Solution:

1. Formula: onto a 2-set $=2^n-2$, since the only maps that fail to be onto are the two constant functions.
2. Here $n=6$, so all functions number $2^6=64$.
3. Remove the $2$ constants: $64-2=62$.

Takeaway: with exactly two outputs, "onto" simply means "not constant", so just subtract $2$ from $2^n$.

Example 3: Number of equivalence relations on $\{a,b,c\}$. Count the equivalence relations on a 3-element set, then extend the idea to a 4-element set.

Solution:

1. Formula: equivalence relations match partitions one-to-one, so the count is the Bell number $B_n$.
2. List the partitions of $\{a,b,c\}$: $\{abc\}$; then $\{ab\},\{c\}$; then $\{ac\},\{b\}$; then $\{bc\},\{a\}$; then $\{a\},\{b\},\{c\}$ — five in all, so $B_3=5$.
3. For a 4-set apply $B_{n+1}=\sum_{k=0}^{n}{}^{n}C_k\,B_k$: $B_4={}^{3}C_0 B_0+{}^{3}C_1 B_1+{}^{3}C_2 B_2+{}^{3}C_3 B_3=1+3+6+5=15$.

Takeaway: equivalence relations are counted by the Bell numbers $1,2,5,15,52,\dots$, so resist the urge to write a power of $2$.

Example 4: Reflexive, symmetric, and both, on a 4-set. On a set with $4$ elements, count the relations that are (i) reflexive, (ii) symmetric, and (iii) reflexive and symmetric together.

Solution:

1. Take $n=4$, so $A\times A$ has $n^2=16$ cells and there are $2^{16}$ relations in all.
2. Reflexive: force the $4$ diagonal cells "in", leaving $16-4=12$ free, so $2^{12}=4096$.
3. Symmetric: the $4$ diagonal cells and the $\dfrac{n(n-1)}{2}=6$ upper-triangle pairs are free, giving $2^{4+6}=2^{10}=1024$.
4. Reflexive and symmetric: diagonal forced in, only the $6$ upper-triangle pairs free, so $2^{6}=64$.

Takeaway: count the freely chosen cells and raise $2$ to that power; the diagonal contributes $n$ and the upper triangle contributes $\dfrac{n(n-1)}{2}$.

Example 5: Even and odd parts of a cubic. Split $f(x)=x^3+3x^2+2x+5$ into its even and odd parts.

Solution:

1. Formula: even part $=\tfrac12\big[f(x)+f(-x)\big]$ and odd part $=\tfrac12\big[f(x)-f(-x)\big]$.
2. Compute $f(-x)=-x^3+3x^2-2x+5$.
3. Even part $=\tfrac12\big[(x^3+3x^2+2x+5)+(-x^3+3x^2-2x+5)\big]=\tfrac12(6x^2+10)=3x^2+5$.
4. Odd part $=\tfrac12\big[(x^3+3x^2+2x+5)-(-x^3+3x^2-2x+5)\big]=\tfrac12(2x^3+4x)=x^3+2x$.
5. Check: $(3x^2+5)+(x^3+2x)=x^3+3x^2+2x+5$, which is $f(x)$.

Takeaway: the even part gathers the even-degree terms and the odd part the odd-degree terms, and this split is unique.

Example 6: Turning a sum into a product. A function satisfies $f(x+y)=f(x)\,f(y)$ for all real $x,y$, with $f(1)=3$. Find $f(x)$ and $f(4)$.

Solution:

1. Formula: $f(x+y)=f(x)f(y)$ forces $f(x)=a^{x}$ with $a=f(1)$.
2. Here $a=3$, so $f(x)=3^{x}$.
3. Therefore $f(4)=3^{4}=81$.

Takeaway: a rule that turns a sum of inputs into a product of outputs is an exponential, and its base is $f(1)$.

Example 7: Turning a product into a sum. For all positive reals, $f(xy)=f(x)+f(y)$ and $f(2)=6$. Find $f(32)$.

Solution:

1. Formula: $f(xy)=f(x)+f(y)$ forces $f(x)=k\ln x$, so $f(1)=0$ and $f(x^p)=p\,f(x)$.
2. Write $32=2^5$, hence $f(32)=f(2^5)=5\,f(2)$.
3. So $f(32)=5\times 6=30$.

Takeaway: a rule that turns a product of inputs into a sum of outputs is a logarithm; powers slide out as multipliers, and $f(1)=0$ always.

Example 8: The reciprocal identity. A polynomial $f$ satisfies $f(x)\,f(1/x)=f(x)+f(1/x)$ for every $x\ne 0$, with $f(2)=9$. Find $f(3)$.

Solution:

1. Formula: the only polynomial solutions are $f(x)=1\pm x^{n}$.
2. Since $f(2)=9>1$, take $f(x)=1+x^{n}$; then $1+2^{n}=9$, so $2^{n}=8$ and $n=3$.
3. Thus $f(x)=1+x^{3}$, giving $f(3)=1+27=28$.

Takeaway: the identity $f(x)\,f(1/x)=f(x)+f(1/x)$ pins $f$ down to $1\pm x^{n}$, and a single known value fixes $n$.