Lemma. For sets $A, B$ with $|X|=|Y|=m \in \mathbb{N}$ there exists exactly $m! = 1 \cdot 2 \cdot \ldots \cdot m$ pairwise distinct bijective maps between $X$ and $Y$.
Proof is left as an exercise.
Looks like the proof has to do with combinatorics but don't know how to make a fist assumption/claim.
Things we can conclude:
- We have $n$ elements from which we want to know the number of ways to choose $k$ elements, thus the size of both our sets $X$ and $Y$ is $\binom{n}{k}$.
- Symmetry Rule for the Binomial Coefficient states that $\binom{n}{k} = \binom{n}{n-k}$. Therefore, we could say that $|X| = \binom{n}{k}$ and $|Y| = \binom{n}{n-k}$
I do not know if that is even useful and, if so, where to go from there.
Liesen, J., Mehrmann, V. 2015. Linear Algebra. Berlin, Germany.: Springer.
Best Answer
HINT: Prove it by induction on $m$. Note that it suffices to assume that $X=\{1,2,\ldots,m\}$. (Why?) The case $m=1$ is trivial. At the induction step consider the number of choices for $f(m+1)$ and then the number of possibilities for $f\upharpoonright\{1,2,\ldots,m\}$.