# How many everywhere defined functions are not $1$ to $1$

I am stuck with the following question, How many everywhere defined functions from S to T are not one to one

S={a,b,c,d,e}
T={1,2,3,4,5,6}


Now the teacher showed that there could be $6^5$ ways to make and everywhere defined function and $6!$ ways of it to be $1$ to $1$ but when I drew them on paper I could drew no more than 30, here are those,
$(a,1),(a,2).........(a,6)$
$(b,1),(b,2).........(b,6)$
$(c,1),(c,2).........(c,6)$
$(d,1)(d,2).........(d,6)$
$(e,1)(e,2).........(e,6)$
Can anyone please help me out with how there are $6^5$ functions?
Thanks

-
@anon: edited it. Thanks :) –  Fahad Uddin Oct 24 '11 at 6:04
I've edited out the negative-ones. –  Gerry Myerson Oct 24 '11 at 6:09

You have produced a complete and correct list of all ordered pairs $(x,y)$, where $x$ ranges over $S$ and $y$ ranges over $T$. However, this is not the set of all functions from $S$ to $T$.

Your list, however, gives a nice way of visualizing all the functions. We can produce all the functions from $S$ to $T$ by picking any ordered pair from your first row, followed by any ordered pair from your second row, followed by any ordered pair from your third row, and so on. We have $6$ choices from the first row. For any of these choices, we have $6$ choices from the second row, for a total of $6\times 6$ choices from the first two rows. For every way of choosing from the first two rows, we have $6$ ways to choose from the third row, and so on for a total of $6^5$.

A function from $S$ to $T$ is a set of ordered pairs, with one ordered pair taken from each row. This view is quite close to the formal definition of function that you may have seen in your course.

For example, we might choose $(a,1)$, $(b,5)$, $(c,1)$, $(d,5)$, $(e,2)$. This gives us the function that maps $a$ and $c$ to $1$, $b$ and $d$ to $5$, and $e$ to $2$.

We can produce the one-to-one functions in similar way from your "matrix." We start by taking any ordered pair from your first row. But then, from the second row, we must pick an ordered pair which is not in the same column as the first ordered pair you picked. So even though there are $6$ choices from the first row, for every such choice, there are only $5$ choices from the second row. Similarly, once we have picked a pair from each of the first two rows, in the third row we must avoid the columns these pairs are in. So we end up with only $6\times 5\times 4\times 3\times 2$ one-to-one functions.

-

What you have in each line is not a function. For example, look at $(a,1)$, which you've counted as a "function." Call it $f(\circ)$. What then are $f(b),f(c),f(d),f(e)$? You can't say. Because simply fixing the correspondance $a\leftrightarrow 1$ does not give you a whole function, it only gives a small piece of one. Here is how to count the total number of one-to-one (bijective) functions $\{a,b,c,d,e\}\to\{1,2,3,4,5,6\}$:

• There are six possible outputs that $a$ could go to. Choose one arbitrarily.
• There are then five possible outputs for $b$ - it can't be the same as $a$ - and that number five is independent of which output was chosen for $a$. Choose the output for $b$ then from this pool.
• Now there are four possible outputs for $c$, by the same token. Choose again.
• $\cdots\cdots\cdots$
• After you have chosen outputs for $a,b,c,d$, the last number remaining must go to $e$ as its output, so there is only one choice to make in this final stage.

Since in each stage the number of choices is independent of which choices were made in the other stages, we can multiply the numbers together to count the total number of bijections: $6!$.

It's easier simply counting the number of functions $S\to T$; there are six stages again (one for each input) and there are six possible outputs for each of $a,b,c,d,e$, so $6^5$ functions in total.

-

You have misunderstood what a function is. $(a,1)$ is not a function defined on $S$, it just tells you where $a$ goes. For a function to be defined on $S$ it must tell you where $a$ goes, and where $b$ goes, and ... and where $e$ goes. Now can you see where $6^5$ comes from?

-
You mean every function should be everywhere defined? –  Fahad Uddin Oct 24 '11 at 6:22
Akito, you used the phrase "everywhere defined" in your question. But, yes, is someone says $f$ is a function from $S$ to $T$, then that means that for every $s$ in $S$ there is a $t$ in $T$ such that $f(s)=t$. –  Gerry Myerson Oct 24 '11 at 12:13

Here is another way of looking at the question. Each function from $S$ to $T$ can be thought of filling balls($S$) into boxes($T$). You have six boxes numbered $1,2,3,4,5$ and $6$ and five balls named $a,b,c,d,$ and $e$. In how many ways can these five balls be placed in those six boxes? Each of the five balls can go to any of the six boxes, so it is $6^5$ (called product rule in combinatorics).

-