8
$\begingroup$

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!

$\endgroup$
6
  • 2
    $\begingroup$ Probably you should include as another example that "everyone knows about" things like how many 11-letter "words" can formed using the 11 letters of MISSISSIPPI (in order to generate examples that are less well known). $\endgroup$ Nov 14 '21 at 17:40
  • 1
    $\begingroup$ @DaveLRenfro I think this example is a bit more sophisticated than what I am looking for, since it requires multiple divisions. I am looking for situations where (without using this language with the students) the set $X$ and the equivalence relation $\sim$ are both easy to identify, so the problem is solved by one division (after counting $X$ and $c$). $\endgroup$ Nov 14 '21 at 17:43
  • 3
    $\begingroup$ There's an interesting pedagogical principle that might be worth teasing out here. I've never liked that books divide problems up into 'multiplication principle' and 'addition principle'. I want students thinking about features of the problem first, not arithmetic operations. But I see that you are doing it the way the books do. I'd like to understand how our thinking differs. $\endgroup$
    – Sue VanHattum
    Nov 14 '21 at 18:39
  • 2
    $\begingroup$ @SueVanHattum I think it would be nice to set up a place where we can have conversations. What do you think about using Discord? I will post about this on Meta. $\endgroup$ Nov 14 '21 at 18:54
  • 1
    $\begingroup$ @SueVanHattum We could chat here if you like: discord.gg/urrYs6Xn $\endgroup$ Nov 14 '21 at 18:58
9
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ This is very nice! $\endgroup$ Nov 14 '21 at 19:00
  • $\begingroup$ What would change if p wasn't ap rime $\endgroup$
    – Buraian
    Dec 11 '21 at 16:33
  • $\begingroup$ @666User666 Let $S_m$ be the number of necklaces of $n$ beads with period $m$, that is, that have a repeating unit $m$ beads long. To find the number of necklaces of $n$ beads with no period less than $n$, we can use inclusion-exclusion. Let $p_1,\ldots,p_k$ be the distinct prime factors of $n$. Then from $\lvert S_n\rvert$ we should subtract $\lvert S_{n/p_i}\rvert$ for each $i$ between $1$ and $k$. There will be intersections among the $S_{n/p+i}$, however, so we have subtracted too much, and will need to add something back. Alternately subtracting and adding, using... $\endgroup$ Dec 14 '21 at 18:42
  • $\begingroup$ ... inclusion-exclusion, gives the desired number. For example, if $n=300$ the distinct prime factors are $2$, $3$, and $5$. We start with $\lvert S_{300}\rvert-\lvert S_{150}\rvert-\lvert S_{100}\rvert-\lvert S_{60}\rvert$. But, for example, $S_{150}$ and $S_{100}$ contain necklaces with period $50$ in common, so these have been subtracted twice and need to be added back. Carrying out the full process, and using $S_m=a^m$, we find that the number of necklaces with period $300$ but no smaller period is $a^{300}-a^{150}-a^{100}-a^{60}+a^{50}+a^{30}+a^{20}-a^{10}$. $\endgroup$ Dec 14 '21 at 18:51
  • $\begingroup$ If $C_n$ denotes the number of necklaces of length $n$ with no period smaller than $n$, then the number of necklaces up to rotational equivalence is $\sum_{d\mid n} C_d/d$. One can show that this equals $\sum_{d\mid n} \varphi(d)a^{n/d}$, where $\varphi$ is Euler's totient function. I believe this is usually derived via Burnside's Lemma or Polya counting, but I'm not prepared to go into that right at the moment. $\endgroup$ Dec 14 '21 at 23:48
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Indeed, the penultimate paragraph in the OP indicates that this is the reason I want simpler examples: to give some experience with thinking about division before developing the formula for combinations. $\endgroup$ Nov 15 '21 at 11:53
  • 1
    $\begingroup$ @StevenGubkin: I know, but that seems like the simplest already haha. I cannot imagine trying to get students to understand the number of non-monochromatic necklaces of beads of $p$ colours if they cannot understand $n$ choose $k$. But I guess you might like the $1$ before $2$ example in my other post, since it is just a bit simpler than $n$ choose $k$. =) $\endgroup$
    – user21820
    Nov 15 '21 at 12:15
  • $\begingroup$ Ya, the answers so far seem to advanced. I am wanting very simple examples, like in my original post. $\endgroup$ Nov 15 '21 at 12:36
  • $\begingroup$ @StevenGubkin: Well there is a simpler form of "1 before 2". How many ways can you put A,B on a row of n seats so that A is on the left of B? Well, n·(n−1)/2. But it's again not really equivalence classes, though the flavour is there. $\endgroup$
    – user21820
    Nov 15 '21 at 12:42
  • 1
    $\begingroup$ Another (essentially equivalent) symmetric approach is to note that choosing $k$ out of $n$ distinct items is equivalent to arranging all the $n$ items in a line (in one of the $n!$ possible orders), taking the first $k$ items and forgetting their order (i.e. divide by $k!$), and also forgetting the order of the remaining $n-k$ items (i.e. divide by $(n-k)!$). $\endgroup$ Nov 15 '21 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.