Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What have you tried so far? –  Jonathan Christensen Jan 22 '13 at 17:53
add comment

1 Answer

up vote 2 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.