Results 1 to 5 of 5

Math Help - number of functions

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    112

    number of functions

    let A ={1,2,3,4,5} and B={6,7,8,9,10}
    then how many non decreasing functions are possible from A to B?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12

    Re: number of functions

    Well... the total number of functions from A to B minus the number of decreasing functions from A to B.
    The total number of functions from A to B is 5^5=3125 and the number of decreasing functions from A to B is \binom{5+5-1}{5}=\binom{9}{5}=126.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    112

    Re: number of functions

    Quote Originally Posted by veileen View Post
    Well... the total number of functions from A to B minus the number of decreasing functions from A to B.
    The total number of functions from A to B is 5^5=3125 and the number of decreasing functions from A to B is \binom{5+5-1}{5}=\binom{9}<br />
{5}=126.
    sir can you explain this step number of decreasing functions from A to B is \binom{5+5-1}{5}=\binom{9}<br />
{5}=126.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: number of functions

    Quote Originally Posted by ayushdadhwal View Post
    let A ={1,2,3,4,5} and B={6,7,8,9,10}
    then how many non decreasing functions are possible from A to B?
    First, I think the answer in reply #2 is incorrect.
    Suppose that you selected ten numbers from set B allowing repeated memberships.
    Here is an example of such a multiset: [9,6,8,6,8].
    I can rearrange that selection this way: [6,6,8,8,9].
    That can be thought of as a non-decreasing function from A\to B.
    Written in permutation notation: \sigma=\binom{1~2~3~4~5}{6~6~8~8~9} so \sigma(3)=8.

    So any multi-selection of five from set B corresponds to non-decreasing function from A\to B.
    There are \binom{5+5-1}{5} such selections.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,791
    Thanks
    693

    Re: number of functions

    Another way to look at it would be:
    A non-decreasing function could hit 1, 2, 3, 4, or all 5 of the values in B. So, if it hits only 1 value, there are 5 functions that would do that.
    If it hits two values, there are \binom{5}{2} different choices for the two values. Since \sigma(1) must go to the lesser number, there are 4 possible choices for numbers n such that \sigma(n) is the least element of A that goes to the higher element of B.
    If it hits three values, there are \binom{5}{3} different choices for the three values, then \binom{4}{2} choices for the two elements in A that will map to the higher two elements.
    If it hits four values, there are \binom{5}{4} different choices for four values, then \binom{4}{3} choices for the three elements in A that will map to the higher three elements.
    Finally, if it hits all five values, there is one possible function that will map it.
    So, adding them all up, we get: 5 + (10)(4) + (10)(6) + (5)(4) + 1 = 126 just as Plato got. (In case you are not familiar with multi-set permutations).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of functions from one set to another?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 8th 2011, 09:46 AM
  2. Replies: 2
    Last Post: August 19th 2010, 09:32 PM
  3. number of functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 16th 2010, 10:23 AM
  4. Replies: 5
    Last Post: October 7th 2008, 12:55 PM
  5. Number of Functions
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 25th 2008, 11:17 AM

Search Tags


/mathhelpforum @mathhelpforum