Results 1 to 9 of 9

Math Help - Suppose the set A has m elements and the set B has n elements. there are 2^mn relatio

  1. #1
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    1

    Suppose the set A has m elements and the set B has n elements. there are 2^mn relatio

    Suppose the set A has m elements and the set B has n elements. there are 2mn relations from A to B and n^m functions from A to B

    if m=n+1,find the number of functions from A onto B.

    the answer is this
    http://i83.photobucket.com/albums/j3...at121712AM.png

    Can someone dumb this down for me so i can understand it?
    Attached Thumbnails Attached Thumbnails Suppose the set A has m elements and the set B has n elements. there are 2^mn relatio-screen-shot-2011-11-27-12.17.12-am.png  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Suppose the set A has m elements and the set B has n elements. there are 2^mn rel

    Can you be precise about what you don't understand? Is it the combinatoric notation, or the terminology like "pre-image"? It gives you the answer right there: n! times (n+1) choose 2. Look here: Binomial coefficient - Wikipedia, the free encyclopedia

    Also, you didn't specify, but I assume you are only considering finite sets. These formulas won't work for infinite sets.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Suppose the set A has m elements and the set B has n elements. there are 2^mn rel

    Addendum: In case you're curious, there are formulas that work with infinite sets, just not the ones given above.

    For an infinite set S, |S|+1 = |S|. The number of functions from S to T = |S|$^|^T^|$ under the definition for cardinal arithmetic, and when |S| = |T| this is equal to 2$^|^S^|$. If we restrict this to onto functions, it is still equal to 2$^|^S^|$. This is because onto functions are a subclass of bijections, and there are a total of 2$^|^S^|$ bijections between any infinite set and itself. (You can show this by using an embedding scheme that labels each bijection from \mathbb{N} to \mathbb{N} with a real number, such that all real numbers between 0.0 and 1.0 are accounted for. Each real in this range may be encoded as a set of naturals ordered sequentially from smallest to largest, where the final digit in each natural corresponds to the digit located at the same point in the real sequence.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    1

    Re: Suppose the set A has m elements and the set B has n elements. there are 2^mn rel

    I guess it is for finite sets. its the notation that usually confuses me. for example when it says (n+1 over 2) does it mean (n+1)P(2)?? It's the stuff in parenthesis im not sure about.

    Could you give an example applying the answer to show its true?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,380
    Thanks
    745

    Re: Suppose the set A has m elements and the set B has n elements. there are 2^mn rel

    let's say A = {a,b,c,d} and B = {s,t,u}. we want to find the number of onto functions f:A→B.

    well, some member of B has 2 pre-images. there are 3 ways (= n) this can happen. having made THAT choice, we have to count the number of ways we can pick two elements of A to go to that member of B. so we need to know how many ways there are to pick 2 things out of 4 things, that number is "4 choose 2" or:

    4!/(2!(4-2)!) = 4!/(2!2!) = 24/((2)(2)) = 24/4 = 6 (this is the "stuff inside the parentheses", which is called a binomial coefficient).

    having decided which 2 elements of A get "doubled up" onto which element of B, we now have to assign the remaining targets for the rest of A.

    we have 2 choices for where to send the 3rd element of A (since one element of B is already spoken for), after which our last choice is already made for us.

    so we have (2)(1) = 2! ways to assign the rest of A, for a grand total of 3(6)(2) = 36 possible onto functions.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Suppose the set A has m elements and the set B has n elements. there are 2^mn rel

    Aquameatwad, the parenthetic notation represents something called a binomial coefficient, and the Wikipedia article I linked you to explains it in depth.

    Here's the theory. If you multiply (x + 1) by itself n times (this is called the binomial power), you will end up with one term for every power of x from 0 to n. The coefficient of the k^t^h term is what "n choose k" gives you, and the notation $${n \choose k}$$ is used to represent it. The binomial power is very common (and useful!) so it pops up all over the place in discrete math.

    The reason we call it "n choose k" is that it just so happens to correspond directly to the number of different unordered ways you can select things from a group of different objects. The result of such a selection is called a combination, and is useful for modeling random processes where order is irrelevant, like flipping a coin twenty times and counting the number of heads.

    If you're building a sequence of things (where the order of choice makes a difference), it's a little different. Each different way you can impose order on a sequence of things is called a permutation of the sequence. There are n! permutations of a finite sequence of length n, if all of the elements are unique. (This becomes a little more complicated if the elements are not unique.) If we choose items from a set, and order matters to us, this is called a sequence without repetition. This is easy to figure out, though, since the items in a set are unique. We just choose the items then multiply the result by k!, which is the number of ways those items could have been permuted (the number of different orders we could have extracted them in).

    There are lots of ways to calculate $${n \choose k}$$, but the easiest to remember is $$\frac{n!}{k!(n-k)!}$$.

    If you're doing a sequence without repetition, this cancels out the k! in the denominator, leaving the simpler equation $$\frac{n!}{(n-k)!}$$.

    Here are some examples of the theory.

    Binomial for n = 3: (x+1)^3 = (x+1)(x+1)(x+1) = x^3 + $\textbf{3x^2}$ + 3x + 1.

    We see $${3 \choose 2}$$ = 3, because the coefficient of $\textbf{x^2}$ is 3. Confirming this with the formula:

    $$\frac{3!}{2!(3-2)!}$$ = $$\frac{6}{2 \times 1} = \textbf{3}$$.

    Confirming this with the process of selection:

    If I have 3 colored balls as {red, green, blue} and select 2 of them, how many different combinations of balls can I get?

    | \{ \{red, green\}, \{red, blue\}, \{green, blue\} \} |$ = \textbf{3}$.

    Finally, confirming the logic of applying this to "how many different functions":

    A function is a special kind of relation (a set of ordered pairs with domain in one place, target in the other). An onto function is called a surjection. If this is a surjection from domain X to target Y, we know three things:

    1) Function means it's right-definite: each $x \in X$ only appears once.
    2) Totality (which is always assumed unless they say "partial function") means it's left-total: each $x \in X$ appears at least once. So, combined this means each $x \in X$ appears exactly once.
    3) Onto means it's right-total: Every $y \in Y$ appears at least once.

    However, it is possible that each y could be the f(x) for multiple x (for finite sets, this would happen if X is larger than Y).

    The intuition is this: let's say you want to build a surjection from X to Y. You can do this by simply selecting one y in Y for each x in X, making certain that you don't leave any y in Y unpaired. But there is only one more element in Y than there is in X (for your problem). We will have to pair exactly one element in Y twice with one of the elements of X.

    Now, the number of ways we can pair all but one of the elements in X with all the elements in Y, leaving none unpaired (this is called a bijection), is simply a permutation of Y. To show this, arbitrarily label each X with successive natural numbers, and choose elements from Y in order, then pair up the choices in the order you get them. It should be clear that the process of permuting Y gives you all possible pairings of X and Y where none is left unpaired.

    There are two bijections from S = \{h, i\} to T = \{j, k\}: \{(h, j), (i, k)\} and \{(h, k), (i, j)\}. If you arbitrarily label h with 1 and i with 2, and select two items in order from T, you either get \{(1, i), (2, j)\}, or \{(1, j), (2, i)\}. There are 2! = 2 ways to select two items in order from T, so there are 2 bijections from S to T.

    So finally, to explain the wording in the solution.

    One element of B has two preimages (it's mapped to by two different things in A). There are n ways we can choose which item in B gets this distinction, and $${n + 1 \choose 2}$$ ways we can choose which two elements of A map to the same item. Once we've done that, we set those aside. Now we have n-1 elements unpaired in A, and n-1 elements unpaired in B, and there are (n-1)! ways to match those up. We multiply the possibilities together, note that $n \times (n-1)! = n!$, and get the resulting equation.

    You should probably read up on the binomial theorem in Wikipedia.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    1

    Re: Suppose the set A has m elements and the set B has n elements. there are 2^mn rel

    Deveno, shouldnt A have 3 elements and B have 4 elements? Or does it not matter?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    1

    Re: Suppose the set A has m elements and the set B has n elements. there are 2^mn rel

    nevermind i get it, m=n+1. doi
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Suppose the set A has m elements and the set B has n elements. there are 2^mn rel

    Quote Originally Posted by Aquameatwad View Post
    Deveno, shouldnt A have 3 elements and B have 4 elements? Or does it not matter?
    It matters, but he's right. A has one more element than B does (look at the problem). If A didn't have at least as many elements as B, you wouldn't be able to build a function "onto" B, where every element of B is in the image of the function. (This follows from functions being right-definite; each x can only give us one f(x).)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 10th 2011, 06:40 PM
  2. [SOLVED] Why are these not elements of W
    Posted in the Advanced Algebra Forum
    Replies: 12
    Last Post: October 22nd 2011, 03:02 PM
  3. Suppose |G|=22. Show G has elements of order 2 and 11.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 14th 2011, 01:49 PM
  4. non-zero elements in E
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: May 5th 2008, 07:33 AM
  5. elements
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: April 20th 2008, 11:52 PM

Search Tags


/mathhelpforum @mathhelpforum