Number of "almost pairing functions" Let $f:[m]\to[n]$ where $n<m$ be an "almost paring function" if $f$ is surjection and $|\{k\in [n] :|f^{-1}[\{k\}]|>1 \}|=1$.
a) how many functions of this sort exists?
My solution: So an almost pairing function is a function that takes $m-n+1$ numbers in $[m]$ to one number in $[n]$ and for the rest of the numbers in $[m]$ it's a $1$-to-$1$ pairing. Thus I believe that to get the number of such functions we first have to choose $m-n+1$ numbers that can go to one of $n$ numbers, and then the rest $n-1$ numbers can go to their permutation. So my answer is $C(m,m-n+1)\cdot n\cdot (n-1)!$
b) Define the set $X$ to be the set of almost pairing functions and the relation $S$ by: $fSg \iff \exists h:[m]\to[m]$ such that $h$ is $1$-to-$1$ and $f=g\circ h$. What is the power of the set $X/S$?
My attempt which I'm not certain of: we still need to pick $m-n+1$ numbers to go to $1$ single number, but now we don't care about the permutations so the answer is $C(m,m-n+1)$?
I'm having some trouble understanding equivalence classes, so even if my solution is correct I'd love to see a more rigorous proof, or the idea of how to do it myself.
Thanks
 A: The answer to the first part is correct, we have $|X|=\binom{m}{n-1}n!$. For the second part let $\mathcal S$ be the symmetric group for $[m]$, i.e. the set of bijections $h:[m]\rightarrow[m]$. Further, let $\mathcal E(f)=\{f\circ h:h\in\mathcal S\}$ be the equivalence group of $f$. Notice that $f\circ h$ is also an almost pairing function for all $h\in\mathcal S$. Also, notice that we have $gSf$ exactly if $g\in\mathcal E(f)$, so $\mathcal E(f)$ is the equivalence class of $f$. Let $\mathcal N=\{i\in[n]:|f^{-1}(i)|=1\}$ and notice that $|\mathcal N|=n-1$, $\mathcal N=\{i\in[n]:|g^{-1}(i)|=1\}$. For $i\in\mathcal N$ we necessarily have $h(g^{-1}(i))=f^{-1}(i)$. Now, let $i\in[n]\setminus\mathcal N$ be the unique element that is hit multiple times. For $a\in g^{-1}(i)$ it doesn't matter how we choose $h(a)\in f^{-1}(i)$, since this preserves $g=f\circ h$. Since we have $|g^{-1}(i)|=|f^{-1}(i)|=m-(n-1)$, this gives $|\mathcal E(f)|=\frac{m!}{(m-(n-1))!}=\binom{m}{n-1}(n-1)!$, respecting that each of the images $g$ for one of the $m!$ bijections $h$ is hit $(m-(n-1))!$ times. Now, since the equivalence classes $\mathcal E(f)$ form a partition of $X$ (no element of $X$ can be in two equivalence classes), we have $|X/S|=|\{\mathcal E(f):f\in X\}|=\binom{m}{n-1}n!/(\binom{m}{n-1}(n-1)!)=n$. Intuitively, given the element $i\in[n]$ that is hit $m-(n-1)$ times, the corresponding equivalence class is composed of all $\binom{m}{n-1}(n-1)!$ functions which do exactly that, namely map $m-(n-1)$ elements to $i$ (and the others uniquely).
