TheCATExam
Sign in

CAT 2024 Slot 1 — QA Question 20

Basics (Functions)Easy

Consider two sets A = {2, 3, 5, 7, 11, 13} and B = {1, 8, 27}. Let f be a function from A to B such that for every element b in B, there is at least one element a in A such that f(a) = b. Then, the total number of such function f is

Answer & solution

  • A

    667

  • 540

  • C

    665

  • D

    537

Solution

Hard

The condition "every bb in BB is hit by some aa" means ff is onto (surjective). Count surjections from a 66-element set onto a 33-element set using inclusion–exclusion: 363^6 total minus those that miss at least one target.

1

Total functions. Each of the 66 elements of AA maps to any of the 33 elements of BB.

total=36=729\begin{aligned} &\text{total}=3^6=729 \end{aligned}
2

Inclusion–exclusion for onto. Subtract functions missing at least one element of BB.

N=∑i=03(−1)i(3i)(3−i)6⇒ N=36−(31)26+(32)16−(33)06(expand)⇒ N=729−3⋅64+3⋅1−0\begin{aligned} &N=\sum_{i=0}^{3}(-1)^i\binom{3}{i}(3-i)^6\\ &\Rightarrow\ N=3^6-\binom31 2^6+\binom32 1^6-\binom33 0^6 \quad\text{(expand)}\\ &\Rightarrow\ N=729-3\cdot64+3\cdot1-0 \end{aligned}
3

Evaluate.

N=729−192+3⇒ N=540\begin{aligned} &N=729-192+3\\ &\Rightarrow\ N=540 \end{aligned}
Number of onto functions=540\text{Number of onto functions}=540

Surjections onto 33 targets =3!×S(6,3)=3!\times S(6,3) where S(6,3)=90S(6,3)=90 is a Stirling number: 6×90=5406\times90=540.

CAT 2024 Slot 1 QA Q20: Consider two sets A = {2, 3, 5, 7, 11, 13} and B = {1, 8, 27}. Let f be a function from A to B such that for e — Solution | TheCATExam