# Numbers of Different type of function

If $A = \{1,2,3,4,5,6,7,8\}$ and $B = \{1,2,3,4,5\}$ . Then The no. of

(1) Into- function from $A$ to $B$

(2) Onto function from $A$ to $B$

(3) Many one function from $A$ to $B$

Although I have a Knowledge of Many one function , Into function and Onto function but cauld not find and appropiate method.

-
What have you tried so far? –  Jonathan Christensen Jan 22 '13 at 17:53

In order to build a function $f$ from $A$ to $B$, you must choose for each $a\in A$ an $f(a)\in B$. There are $5$ possible choices for $f(a)$, and you make this $5$-way choice $8$ times, so by the multiplication principle there are $5^8$ ways to build the function. In other words, there are altogether $5^8=390,625$ functions from $A$ to $B$.

$A$ has more elements than $B$, so if $f$ is any function from $A$ to $B$, the pigeonhole principle guarantees that there will be distinct $a_1,a_2\in A$ such that $f(a_1)=f(a_2)$. Thus, every function from $A$ to $B$ is many-to-one, so there are $5^8$ such functions.

Counting the onto functions is a little harder. One way is to use an inclusion-exclusion argument. Using the same reasoning as in the first paragraph, we see that there are $4^8$ functions from $A$ to $\{1,2,3,4\}$; these obviously do not map $A$ onto $B$. Similarly, there are $4^8$ functions from $A$ to $\{1,2,3,5\}$, $4^8$ functions from $A$ to $\{1,2,4,5\}$, $4^8$ from $A$ to $\{1,3,4,5\}$, and $4^8$ from $A$ to $\{2,3,4,5\}$. If we subtract all of these functions from the total of $5^8$, we get $5^8-5\cdot4^8$ functions. However, we’ve subtracted too much: a function from $A$ to $\{1,2,3\}$, for instance, got subtracted once as a function from $A$ to $\{1,2,3,4\}$ and once again as a function from $A$ to $\{1,2,3,5\}$. It should have been subtracted only once, not twice, so we have to add it back in. There are $3^8$ functions from $A$ to $\{1,2,3\}$, so we have to add back in $3^8$. But $\{1,2,3\}$ isn’t the only $3$-element subset of $B$: $B$ has $\binom53$ $3$-element subsets, and we have to add back in $3^8$ for each of them, so correcting for all of them gives us

$$5^8-\binom544^8+\binom533^8\;.\tag{1}$$

Unfortunately, once again we’ve overcorrected. If you count carefully, you’ll find that every function from $A$ to $\{1,2\}$ has now been counted once in the $5^8$ term, subtracted $3$ times in the $\binom514^8$ term (because $\{1,2\}$ is a subset of $3$ different $4$-element subsets of $B$), and added back in $3$ times in the $\binom523^8$ term (because $\{1,2\}$ is a subset of $3$ different $3$-element subsets of $B$). Thus, it’s still being counted in $(1)$, and we don’t want it, so it has to be subtracted. There are $2^8$ functions from $A$ to $\{1,2\}$, and there are $\binom52$ $2$-element subsets of $B$, so we have to subtract $2^8\binom52$, leaving

$$5^8-\binom544^8+\binom533^8-2^8\binom52\;.\tag{2}$$

This is almost right, but once again we’ve overcorrected: the five constant functions from $A$ to $B$ have been counted once in the first term of $(2)$, subtracted $\binom43=4$ times in the second term, added back in $\binom42=6$ times in the third term of $(2)$, and subtracted $\binom41=4$ times in the last term of $(2)$, so altogether they’ve been counted $-1$ times: they’ve been subtracted once too often and must be added back in. The final total is

$$5^8-\binom544^8+\binom533^8-2^8\binom52+1^8\binom51=126,000$$

onto functions.

Since $A$ and $B$ are small sets, you can also count the onto functions by brute force. Start by enumerating the partitions of $A$ into $5$ parts. Either there is one part of size $4$ and four of size $1$; or there is a part of size $3$, a part of size $2$, and three parts of size $1$; or there are three parts of size $2$ and two of size $1$; there are no other possibilities.

• $(4,1,1,1,1)$: There are $\binom84$ ways to choose $4$ members of $A$ to make up the large part. There are then $5!$ ways to assign function values to the $5$ parts of the partition, so there are $\binom835!$ onto functions of this type.

• $(3,2,1,1,1)$: There are $\binom83\binom52$ ways to choose which members of $A$ will belong to which parts, and there are then $5!$ ways to assign function values to the $5$ parts, for a total of $\binom83\binom525!$ onto functions of this type.

• $(2,2,2,1,1)$: There are $\binom82$ ways to choose the two singletons. Now consider the remaining $6$ elements of $A$. There are $5$ ways to choose which one will be paired with the smallest of these $6$ numbers. There are then $3$ ways to choose which of the remaining $4$ elements will be paired with the smallest remaining number, and that completely determines the pairing of the $6$ elements. Each partition of $A$ can have function values assigned in $5!$ ways, so we get a total of $\binom82\cdot5\cdot3\cdot5!$ onto functions of this type.

The grand total is therefore

$$\left(\binom84+\binom83\binom52+\binom82\cdot15\right)\cdot5!=126,000\;.$$

If you want the number of functions from $A$ strictly into $B$, i.e., the number that are not onto, just subtract the onto functions from the total of all functions from $A$ to $B$.

-