This is a Test of Mathematics Solution Subjective 46 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.

Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

## Problem

A *function* \(f\) from set \(A\) into set \(B\) is a rule which assigns each element \(x\) in \(A\), a unique (one and only one) element (denoted by \(f(x)\) in \(B\). A function of set from \(A\) into \(B\) is called an *ont*o function, if for each element \(y\) in \(B\) there is some element \(x\) in \(A\), such that \(f(x)=y\). Now suppose that \(A =\) {\(1,2,\cdots,n\)} and \(B=\){\(1,2,3\)}. Determine the total number of onto functions of \(A\) into \(B\).

## Sequential Hints

(*How to use this discussion:* **Do not read the entire solution at one go. First, **read more on the **Key Idea, **then give the problem a try. **Next, **look into **Step 1 **and give it another try and so on.)

### Key Idea

This is the generic use case of **Inclusion-Exclusion Principle. **Read on this from Wikipedia

### Step 1

**1** may map to 1, 2, or 3 (3 choices). For each of these three choices, **2 **may map to 1, 2, or 3 (again three choices. Hence 3 choices again. How many functions are possible in total? Can you delete the functions which are **not onto **from the total number of functions?

Try the problem with this hint before looking into step 2. Remember, no one learnt mathematics by looking at solutions.

Your answer is incorrect. For example take n=4, Total number of onto functions are 36 but your formula gives 24.

You are correct. We fixed the solution.