2

Let A be the set {1,2,3,4,5,6}. How many functions from A to A are there such that the range of f has exactly 5 elements?

Ruddie
  • 436

1 Answers1

2

If a function $A \to A$ has a range of cardinal $5$, then there are exactly two distinct elements $(x,y) \in A^2$ with the same image by $f$. There is also an element $c$ in $A$ that is not reached by $f$. If you fix these data, let say $(x,y,c) \in A^3$ such that $x < y$, then such a function is equivalent to a permutation of $B=\{1,2,3,4,5\}$, since if you remove $x$ for example (you could remove $y$, there's just an arbitrary choice to make) from the domain and $c$ from the range, and then relabel both from $1$ to $5$ you get a permutation of $B$. Conversely, $(x,y,c)$ being fixed, if I give you a permutation of $B$, you can reconstruct the corresponding function $f:A \to A$ such that $f(x)=f(y)$ and $range(f)=A-\{c\}$ because you know exactly how the domain and codomain has been relabeled.

So, $(x,y,c)$ being fixed with $x < y$, you have $5!$ such functions. Now, the couple $(x,y)$ and the element $c$ can be choosen independently. You have $\frac{n(n-1)}{2}$ choices for couples $(x,y) \in \{1,\ldots,n\}^2 \mid x < y$ (it's a standard result) and $n$ choices for $c$, where here $n=6$.

So I would say $5! \times 6 \times \frac{6(5)}{2}=10 800$

yago
  • 2,120