Results 1 to 5 of 5

Math Help - Counting functions problem 4

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244

    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) \neq8?

    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}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by oldguynewstudent View Post
    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} ...(?)
    a) How many have f(3)=8? How many have f(3) \neq8?

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

    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

    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

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

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

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244
    Quote Originally Posted by Jhevon View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting functions on the set {1, 2, 3}
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 27th 2011, 12:32 PM
  2. Counting onto functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 27th 2011, 03:23 AM
  3. Counting Zeroes of Complex Functions
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: November 14th 2010, 02:12 AM
  4. Counting Problem Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2010, 06:20 PM
  5. Replies: 3
    Last Post: April 13th 2009, 06:42 PM

Search Tags


/mathhelpforum @mathhelpforum