Simple combinatorics problems using division

Question

I would like to introduce counting principles associated with each of the 4 basic operations (addition, subtraction, multiplication, and division) before introducing permutations and combinations in my Discrete Math course.

It is easy for me to come up with lots of simple problems involving the first three operations, but coming up with natural division problems is proving difficult for me.

Here are a few I have come up with:

1. Count the number of edges and vertices of the icosahedron. If you overcount the number of vertices and edges by treating each of the 20 triangles as distinct, we get $60$ vertices and $60$ edges. However, each edge of the icosahedron corresponds to $2$ of the edges we have counted: hence there are really $60 \div 2 = 30$ edges. Similarly , each vertex of the icosahedron corresponds to $5$ of the vertices we overcounted. Hence there are $60 \div 5 =12$ vertices.
2. 5 people sit around a round table. We do not care about their exact position: only their clockwise arrangement around the table. How many seating arrangements are possible? First over count the number of arrangements by keeping track of their exact position in 5 chairs. There are $5!$ such possibilities. However, $5$ exact seating assignments correspond to each clockwise arrangement. So there are $5! \div 5 = 4!$ such clockwise arrangements.
3. The "handshake" problem is another good one: we need to divide by $2$ to address overcounting.

In general, we use division when we want to count the number of elements of $S$, and we can recognize that $S$ is bijective with $X/ \sim$ for some easier to count set $X$ and an equivalence relation $\sim$ whose equivalence classes all have the same cardinality $c$. Then we count $|S| = |X| \div c$.

I think this is an important counting principle. In particular, I want students to have exposure to this idea before we get the formula for combinations, which involves first counting the number of permutations and then dividing by the number of permutations which correspond to the same combination.

Please contribute as many natural elementary "division" combinatorics problems as you can invent!

Answer 1

You can do necklaces composed of colored beads. For simplicity the number of beads needs to be prime. If there are to be $p$ beads with $a$ choices of color, then there are $a^p$ ways to arrange the colors if one bead is identified as the origin. Since $p$ is prime, the only necklaces with repeating color arrangements are the monochromatic necklaces, of which there are $a$. So the number of non-monochromatic arrangements is $a^p-a$ and the total number of necklaces where rotated arrangements are considered equivalent is $$ a+\frac{a^p-a}{p}. $$ This nicely proves the non-trivial fact that $a^p-a$ is divisible by $p$, which is Fermat's little theorem.

Answer 2

$\def\lfrac#1#2{{\large\frac{#1}{#2}}}$The number of permutations of $[1..n]$ in which $1$ comes before $2$ is just $\lfrac12n!$ if $n ≥ 2$. Clearly the equivalence relation is to consider reversals to be the same, though I would not quite say that the desired configurations are the equivalence classes, since each is rather a representative of a class. This fact, however, is useful for the following harder problem.

The number of bracelets made from $n$ distinct beads, considering it to be invariant under rotation or flipping, is $\lfrac12(n-1)!$ if $n ≥ 3$. This is a good example that demonstrates that boundary cases are important. Also, it is quite impossible to define what a bracelet even is without using the equivalence relation. Here we have $n!$ permutations of the beads, and we consider two of them to be equivalent iff one can be obtained from the other by rotations and/or flips. To count the equivalence classes, we can use the powerful technique of canonicalization, which is the idea of finding a useful canonical form. For this problem, given any permutation, its canonical form is obtained by rotating it to make $1$ at the front and then reversing the rest if necessary to make $2$ come before $3$. Each equivalence class has exactly one canonical form, because every sequence of rotations/flips is equivalent to a sequence of rotations and then at most one flip, so any two canonical forms in the same class must be identical. Also, canonical forms in different classes must be different by definition of the classes. Thus we just have to count canonical forms, which yields the answer by the earlier fact.

Answer 3

Just in case this is not obvious, obtaining the general formula for number of ways to choose $k$ of $n$ distinct items can be done by this technique. First choose a sequence of $k$ distinct items from those, and then apply the $k!$-to-$1$ mapping from those sequences to sets of $k$ items, erasing their ordering.$\def\lfrac#1#2{{\large\frac{#1}{#2}}}$ Since there are $\lfrac{n!}{(n-k)!}$ sequences, the desired number of ways is $\lfrac{n!}{k!·(n-k)!}$.

There is also a more symmetric proof of the same formula: The desired number of ways is simply the number of $n$-digit binary strings with exactly $k$ ones. Well, just label all the zeros $0_1,0_2,...0_{n-k}$ and all the ones $1_1,1_2,...,1_k$, and the number of permutations of these is just $n!$. Now erase the labels, which is a $(n-k)!·k!$-to-$1$ mapping onto the desired set that you want to count.