Results 1 to 3 of 3

Math Help - Please help with surjective fuctions URGENT!

  1. #1
    Newbie
    Joined
    Feb 2013
    From
    australia
    Posts
    22
    Thanks
    1

    Please help with surjective fuctions URGENT!

    Let m ≥ n and let A = {1,2,...,m} and let B = {1,2,...,n}. In this exercise you will determine a formula for the number of surjective functions from A to B. For each i ∈ B, let Ai denote the set of all functions f : A → B such that i is not in the image of f, that is, for all x ∈ A we have f(x) 6= i. Thus the set of all functions from A to B which are not surjective is A1 ∪ A2 ∪ иии ∪ An.

    1. a) Let 1 ≤ k ≤ n. In how many ways can we choose integers i1,i2,...,ik such that 1 ≤ i1 < i2 < иии < ik ≤ n?

    b) Let 1 ≤ i1 < i2 < иии < ik ≤ n. Show that |Ai1 ∩ Ai2∩ иии ∩ Aik| = (n − k)^m.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1

    Re: Please help with surjective fuctions URGENT!

    Quote Originally Posted by juliie View Post
    Let m ≥ n and let A = {1,2,...,m} and let B = {1,2,...,n}. In this exercise you will determine a formula for the number of surjective functions from A to B. For each i ∈ B, let Ai denote the set of all functions f : A → B such that i is not in the image of f, that is, for all x ∈ A we have f(x) 6= i. Thus the set of all functions from A to B which are not surjective is A1 ∪ A2 ∪ иии ∪ An.
    1. a) Let 1 ≤ k ≤ n. In how many ways can we choose integers i1,i2,...,ik such that 1 ≤ i1 < i2 < иии < ik ≤ n?

    b) Let 1 ≤ i1 < i2 < иии < ik ≤ n. Show that |Ai1 ∩ Ai2∩ иии ∩ Aik| = (n − k)^m

    It appears to me that you do indeed understand the process.

    Thus I will give you the final answer, from which I hope you can put together your answer.

    \sum\limits_{k = 0}^m {\left( { - 1} \right)^k \binom{n}{k}\left( {n - k} \right)^m }  = n^m  - \left( {\sum\limits_{k = 1}^m {\left( { - 1} \right)^{k - 1} \binom{n}{k}\left( {n - k} \right)^m } } \right)
    Last edited by Plato; February 3rd 2013 at 05:59 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2013
    From
    australia
    Posts
    22
    Thanks
    1

    Re: Please help with surjective fuctions URGENT!

    Thank you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. prove that if g o f is surjective then g is surjective
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 18th 2011, 10:41 AM
  2. Matlab - Fuctions/Scripts
    Posted in the Math Software Forum
    Replies: 1
    Last Post: January 14th 2010, 11:08 AM
  3. Inverse Of Fuctions
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: September 20th 2009, 04:48 PM
  4. Exponential Fuctions
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: December 10th 2007, 01:06 PM
  5. Urgent Help Quadratic Fuctions/Relations
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 26th 2007, 01:26 PM

Search Tags


/mathhelpforum @mathhelpforum