7

If $A$ has $n$ elements, how many functions are there from $A$ to $A$? How many bijective functions are there from $A$ to $A$.

So for the first part of the question since A isn't bijective, doesn't that mean there are $n^n$ possibilities? So for the second part of the question, since it is bijective means for injectivity it must be one-to-one. therefore wouldn't there be $n!$ functions.

Can anyone confirm?

Cookie
  • 13,532
kero
  • 1,814
  • 1
    Yup. That is correct. – MarkG Feb 21 '15 at 22:42
  • 1
    As noted, it is correct except for the first part; to highlight this, consider how many functions there are from $A$ to $A$ that are not bijective. You know there are $n^n$ functions from $A$ to $A$ in total and that there are $n!$ bijective functions. Thus, the number of functions from $A$ to $A$ that are not bijective is $n^n-n!$. Thus, if you really followed your reasoning at the beginning of the problem that "$A$ isn't bijective" (the functions from $A$ to $A$, that is), then you would end up with $n^n-n!$, not $n^n$. – Daniel W. Farlow Feb 21 '15 at 22:54
  • 2
    $A$ is a set, not a function, so "$A$ isn't bijective" isn't what you meant to write, kero. – Gerry Myerson Feb 21 '15 at 23:22

1 Answers1

5

Well, for the first part, you do not known "$A$ is not bijective" (what you meant to say was that the function from $A$ to $A$ was not bijective, but this is still not right)--that is simply one of the function possibilities. You computed $n^n$ because there are $n$ choices for the first element to map to, $n$ choices for the second element to map to, etc., leaving you with $n^n$ choices in all.

For the other part, bijectivity, you have $n$ choices for the first element to map to, $n-1$ choices for the second element to map to, etc., leaving you with $n!$ choices in all.

I believe that is what your reasoning was, except for the first part (which only needed a very modest amount of tweaking).

Daniel W. Farlow
  • 22,531