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:
- 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.
- 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.
- 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!