Results 1 to 2 of 2

Math Help - Discrete Math!

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    124

    Discrete Math!

    1. (a) Use the product rule to prove that the number of functions from an n-element set to an m-element set is m^n.

    (b) Use a counting argument to show that the multinomial coefficient
    C(mn; n, n,..., n) is between m^n and m^(mn).

    2. Suppose that S is a subset of {1, 2,..., 2n} of size n+1.
    (a) Show that S must contain two integers a and b such that gcd(a,b)=1.

    (b) Show that S must contain two integers c and d such that c divides d.

    I'm no good at "showing" and "proving" so any help is much appreciated...thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1
    Quote Originally Posted by noles2188 View Post
    1. (a) Use the product rule to prove that the number of functions from an n-element set to an m-element set is m^n.
    For starters, here's a solution for 1. (a).

    A function is a mapping which assigns, to every element from the starting set, in this case the n-element set, exactly one element from the target set, in this case the m-element set.

    As this mapping has to be done for each of the n elements from the starting set, or domain, we might as well line all those elements up and see which elements from the codomain (or target set) can be assigned to them.

    To the first element of the domain, we may assign any of m elements of the codomain. Likewise, to the second, third,..., n-th element we can also assign any of the m elements from the codomain, as there are no restrictions.

    So, there are n elements in the domain, and to each one of them, via different functions, we may assign any of those m elements from the target set. From this and the product principle, it follows that there are \underbrace{m\cdot m \cdot \cdot \cdot m}_{\text{n times}} = m^n different functions from a n-element set to a m-element set.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete math
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 22nd 2008, 12:56 AM
  2. Help me, I am new to discrete math
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 25th 2008, 05:15 PM
  3. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 8th 2007, 10:07 AM
  4. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: April 26th 2007, 08:49 AM
  5. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 26th 2007, 12:01 AM

Search Tags


/mathhelpforum @mathhelpforum