Edit #2: Although it is possible to state all this in the simpler language of equivalence relations, one of my favorite ways to show that one integer divides another is to show that there exist a pair of groups $H, G$ with the corresponding cardinalities, one of which is a subgroup of the other. I know a few examples related to the symmetric groups in particular:
$S_{m+n}$ contains the subgroup $S_m \times S_n$, hence $m! n! | (m+n)!$.
$S_{mn}$ contains the subgroup $S_m \wr S_n$, hence $m!^n n! | (mn)!$. (See also the Young tableaux example I wrote about above.)
The Sylow $p$-subgroups of $S_n$ are the iterated wreath product of cyclic groups of order $p$, as follows: divide $n$ up into $\lfloor \frac{n}{p} \rfloor$ blocks of $p$ elements and consider the permutations which preserve these blocks, then divide the blocks up into $\lfloor \frac{n}{p^2} \rfloor$ blocks and toss in permutations of these blocks, etc. Consequently $v_p(n!) = \sum_{k \ge 1} \lfloor \frac{n}{p^k} \rfloor$.
