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

Printable View

November 26th 2011, 09:20 PM
Aquameatwad

1 Attachment(s)

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?http://www.mathhelpforum.com/math-he...isc/pencil.png
November 26th 2011, 10:09 PM
Annatala

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.
November 26th 2011, 11:46 PM
Annatala

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.)
November 27th 2011, 07:30 AM
Aquameatwad

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?
November 27th 2011, 08:42 AM
Deveno

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.
November 27th 2011, 09:34 AM
Annatala

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. (Nod)
November 27th 2011, 09:57 PM
Aquameatwad

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?
November 27th 2011, 10:16 PM
Aquameatwad

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
November 27th 2011, 10:18 PM
Annatala

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

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