Number of Onto Functions (TOMATO Subjective 46)

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 onto 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\).

Solution: For every \(y\in B\), \(x\) can take values from the \(n\) numbers in \(A\). But they have to be unique, so the first \(y_1\) can have \(n\) pre-images, \(y_2\) can have \((n-1)\) pre-images and so on.

Thus in this case, the total number of possible functions is given by : \(n(n-1)(n-2)\).

Leave a Reply

Your email address will not be published. Required fields are marked *