How to explain combinatorical principles like the rule of product to students who "just don't get it"?

Question

I assist in courses that provide mathematical background to computing science students. Every year, there are some who "just don't get" (in their words) concepts like the rule of product or the corollary that there are $p^n$ options to choose $n$ times from $p$ options (e.g. colouring $n$ fields with $p$ colours, no restrictions). Are there some metaphors from programming that may help these students?

Answer 1

This doesn't call for a metaphor from programming. It's rather the opposite, you get it for programming applications such as the number of times through a nested loop because you get the math.

For the product rule, there's a pretty natural geometric presentation. If there are $p$ choices for A and $q$ choices for B, place the choices for A in rows and the choices for B in columns:

$$\begin{array}{c|c|c|c|c|} & B=1 & B=2 & \ldots & B=q \\ \hline A=1 & * & * & \ldots & * \\ \hline A=2 & * & * & \ldots & * \\ \hline \vdots & \vdots & \vdots & \ddots & \vdots \\ \hline A=q & * & * & \ldots & * \\ \hline \end{array}$$

There are $p \times q$ stars in that table. You might relate this to the area of a rectangle. Make sure you draw all the cells as identically-sized squares (unlike my figure above!), say that the length of the side of the square is the length unit, then the total area not including the labels is the number of cells and that's $p \times q$.

In the special case where $p = q$, you get $p^2$. If you add a third choice that also has $p$ possibilities, you can still present it visually as a 3-dimensional model, although it's harder and you can expect some students to have a hard time. Show how three choices with $p$, $q$ and $r$ possibilities respectively give you a total of $p \times q \times r$ possibilities. With the same number of possibilities $p$ for each choice, you get $p^3$.

The numbers increase pretty fast, so it soon becomes unwieldy to count them all. Now is a good opportunity to demonstrate how to go from the two-choice case (two dimensions) to the three-choice case (three dimensions). When you add another dimension of length $r$ to $p \times q$, the number of choices is multiplied by $r$. When you add another dimension of length $r$ to $p \times p$, the number of choices is multiplied by $p$.

At this point you've discreetly planted the seed of the idea of recursion. “When you add another dimension, …” — that's the induction step. Each time you add a new dimension, with $p$ choices in each dimension, the total number of choices is multiplied by $p$.

There are $p^2$ choices with $2$ dimensions, $p^3$ choices with $3$ dimensions. Oh and by the way there are $p$ choices with $1$ dimension, and $p = p^1$. $1 \mapsto p^1$, $2 \mapsto p^2$, $3 \mapsto p^3$, can you see a pattern? (You may or may not mention $p^0$ at this point, depending on whether you think students will get it.)

And the formula corresponds to the induction pattern: $p^{n+1} = p^n \times p$.

Answer 2

Yes, there are. For the rule of product, one can use nested for loops. For example, when one has to choose from 5 pairs of jeans and 7 shirts, you could use a loop like the following to list all the options:

for (Jeans j : jeans) {
    for (Shirt s : shirt) {
        print(j, s);
    }
}

You can then ask how often the inner loop loops and how often the outer one loops. The student then usually understands he should multiply to get the total number of printed pairs.

I do not know of a programming analogy for the power case (ideas welcome), but as this is an extension of the rule of product it is usually explained rather easily: the $n=2$ case relates to the for loops above, so we would have $p\cdot p$. For $n=3$, we would add another loop, hence $p\cdot p\cdot p$. For $n=4$, we would get $p^4$, etc.

Answer 3

I will cover “colouring n fields with p colours, no restrictions”, as the first part was covered by @Keelan.

Number bases

There are at least 2 special cases that they should already know: “How many values in an n bit binary number?”, and “How many values in an n digit denary number?”

Ask them to answer for specific examples e.g. 1 bit, 2 bit → 8 bit. Create a table. Then find a pattern, and generalise to write a formula [$2^n$]. Then add a column for base 10, and maybe base 8, and 16 (if they have done these, in CS class). Now get them to find a pattern again, and generalise [$b^n$ where $b$ is number base, and $n$ in number of bits]

Then link this to non-numberbase, problems: generalise to colours.