Counting functions problem 4

Printable View

July 3rd 2010, 10:36 AM
oldguynewstudent

Counting functions problem 4

Could someone please check my answers for the following problems, especially b?

Consider the possible functions f:[7] $\longrightarrow$ [9]?

a) How many have f(3)=8? How many have f(3) $\neq$ 8?

There is one object being distributed to one recipient for f(3)=8, plus 6 objects being distributed to 9 recipients. So there are $1+9^{6}$ possible functions that have f(3)=8. For the second part of the question, $f(3)\neq8$ has 8 different functions plus 6 objects being distributed to 9 recipients. So there are $8+9^{6}$ possible functions that have $f(3)\neq8$ .

b) How many have $f(1) \neq5$ and are one-to-one?

In this case we have 8 possible functions for $f(1) \neq5$ plus $(9)_{6}= 8+(9)_{6}$ .

c) How many have $f_{i}$ even for all i?

There are 4 even numbers in the Codomain, which gives $4^{7}$ distributions of 7 objects to 4 recipients.

d) How many have $rng(f)=\{5,6\}$ ?

That would be 7 objects distributed to 2 recipients, so $2^{7}$ .

e) How many in which $f^{-1}$ is not a function?

This would be the same as the total number of distributions of 7 objects to 9 recipients minus the number which have a one-to-one relationship which would be $(9)_{7}$ .So the answer is $9^{7}-(9)_{7}$ .
July 3rd 2010, 12:55 PM
Jhevon

Quote:

Originally Posted by oldguynewstudent

Could someone please check my answers for the following problems, especially b?

Consider the possible functions f:[7] $\longrightarrow$ [9]?

I take it [7] = {1,2,3,4,5,6,7} and [9] = {1,2,3,4,5,6,7,8,9} ...(?)

Quote:

a) How many have f(3)=8? How many have f(3) $\neq$ 8?

There is one object being distributed to one recipient for f(3)=8, plus 6 objects being distributed to 9 recipients. So there are $1+9^{6}$ possible functions that have f(3)=8. For the second part of the question, $f(3)\neq8$ has 8 different functions plus 6 objects being distributed to 9 recipients. So there are $8+9^{6}$ possible functions that have $f(3)\neq8$ .

why are you adding? you should be multiplying...

Quote:

b) How many have $f(1) \neq5$ and are one-to-one?

In this case we have 8 possible functions for $f(1) \neq5$ plus $(9)_{6}= 8+(9)_{6}$ .

I am not familiar with the notation you are using. $(9)_6 = _9C_6$ ?

Anyway, I would disagree. We have 8 choices for what to map 3 to. Having made that choice, we again have 8 choices to map the second element to, then 7, then 6, then 5, etc. The total number of functions with this criteria, therefore, is $8^2 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3$

Quote:

c) How many have $f_{i}$ even for all i?

There are 4 even numbers in the Codomain, which gives $4^{7}$ distributions of 7 objects to 4 recipients.

i agree

Quote:

d) How many have $rng(f)=\{5,6\}$ ?

That would be 7 objects distributed to 2 recipients, so $2^{7}$ .

I agree

Quote:

e) How many in which $f^{-1}$ is not a function?

This would be the same as the total number of distributions of 7 objects to 9 recipients minus the number which have a one-to-one relationship which would be $(9)_{7}$ .So the answer is $9^{7}-(9)_{7}$ .

what is your definition of $f^{-1}$ here? Because, unless we restrict the domain somehow, the inverse will technically never be defined.
July 3rd 2010, 01:33 PM
oldguynewstudent

Quote:

Originally Posted by Jhevon

I take it [7] = {1,2,3,4,5,6,7} and [9] = {1,2,3,4,5,6,7,8,9} ...(?)

Yes this is correct

why are you adding? you should be multiplying...

Consider [3] $\longrightarrow$ [4] with f(2)=3
We then have {1,3} $\longrightarrow$ {1,2,3,4}. This gives $4^2$ but then we have the additional f(2)=3. This would be added on wouldn't it?

I am not familiar with the notation you are using. $(9)_6 = _9C_6$ ?

No this stands for $_9P_6$

Anyway, I would disagree. We have 8 choices for what to map 3 to. Having made that choice, we again have 8 choices to map the second element to, then 7, then 6, then 5, etc. The total number of functions with this criteria, therefore, is $8^2 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3$

Then I would need to multiply by the 8 instead of adding it and would agree except for the final factor of 3

I agree

what is your definition of $f^{-1}$ here? Because, unless we restrict the domain somehow, the inverse will technically never be defined.

$f^{-1}$ would be the inverse relation. Then how many would not be functions?
July 3rd 2010, 01:41 PM
Jhevon

No, you would not add, you would multiply. In the case with fixed f(2), you multiply by 1. In all case, f(2) = 3, it wouldn't need to be added. It's already covered in the $4^2$ cases you mentioned. Actually list all the possible functions with this criteria and you will see.

Quote:

Originally Posted by oldguynewstudent

$f^{-1}$ would be the inverse relation. Then how many would not be functions?

How are you defining inverses though. Here, at most 7 elements of the codomain of f would be used. Thus, the inverse function would have 2 elements in its domain that is not used. This is illegal, all elements in the domain of a function must map to something, and a function has an inverse iff it is one-to-one AND onto. Clearly there are no onto functions from [7] to [9], and so technically, you can't have an inverse.

Now, if we are simply saying that the "inverse" here (which is bad grammar, you should just call the function by another name), is just a function from [9] to [7], then we could count the number of functions.
July 3rd 2010, 01:58 PM
Jhevon

Listing 16 functions might get boring... lets do one where we can actually count easily:

Consider the functions from $\displaystyle [2] \longrightarrow [3]$

How many have $\displaystyle f(2) \ne 3$ ?

Short hand: well, there are 2 choices for 2 to map to. For each of those choices, there are 3 that 1 can map to. Hence, the total such functions is 2*3 = 6

Here they are: $\displaystyle \{ (1,1), (2,1) \},~\{ (1,1), (2,2) \},~\{ (1,2), (2,1) \},~\{ (1,2), (2,2) \},~\{ (1,3), (2,1) \},~\{ (1,3), (2,2) \}$

If we had followed your method, the answer would be: 1 has 3 choices, "plus" the two that 2 can map to. Giving 5 functions... and the error gets larger the more elements we use.

Are you seeing why we need to multiply?