MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 added 963 characters in body; added 60 characters in body

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$.

• 2 added 490 characters in body

An obvious choice is the enumeration of orbits of finite group actions, which show up everywhere in middle- and high-school competitions in disguise. The "cute" example here is coloring a cube or a regular polygon up to rotation. I have written a few blog posts on the subject and there are several examples given in the third post. One of my favorite applications here is Lucas' theorem, and once you bring that up you can casually mention the Sierpinski triangle as well.

Edit: And again I feel the need to tell you things most AoPSers already know, but another nice class of examples is provided by the application of linear algebra over $\mathbb{F}_2$ to problems in combinatorics, see e.g. this post by Tim Gowers or Jacob Steinhardt's excellent solution to USAMO 2008 #6.

1 [made Community Wiki]

An obvious choice is the enumeration of orbits of finite group actions, which show up everywhere in middle- and high-school competitions in disguise. The "cute" example here is coloring a cube or a regular polygon up to rotation. I have written a few blog posts on the subject and there are several examples given in the third post. One of my favorite applications here is Lucas' theorem, and once you bring that up you can casually mention the Sierpinski triangle as well.