Posted in Combinatorics

What makes counting problems difficult

I don’t have the numbers but I think not many will disagree with me that among those who like mathematics and find joy in the challenge of solving math problems, only very few will also like to solve combinatorial or counting problems. And if I may be allowed to push my observation a bit further, those who are more inclined to algebra are the ones who have more aversion to problems that asks them to count.

Indeed, combinatorial problems are odd. Unlike other mathematics problems, these type of problems cannot easily be categorized and solved with predictable algorithms. Each problem always seems to be a case in itself. Knowing all the formulas for different cases of permutations and combinations is not a guarantee that one will be able to solve these problems. For many, these are only useful if the problem already explicitly asks for number of permutations and combinations. And when indeed the problem says so, one still has to decipher other conditions and the assumptions embedded in the context. Knowing when to add or multiply is also difficult, if not the most difficult part. Knowing when one already double counted also requires depth of understanding not only of the formulas but also of the context of the problem. Of course for some these are also the very reason why they love to solve counting problems.

Take the case of this family of problems:

 

  1. How many three-digit numbers can you form from the digits, 5, 6, 7, 8, and 9? (This requires direct application of the permutation formula or better, the multiplication principle.)
  2. How many three-digit numbers are there in all? (That you will choose from 0 to 9 is implied only plus you ask yourself how about 027? Is it a 3-digit number of a 2-digit number?)
  3. How many numbers can be formed from 5, 6, 7, 8, and 9?
  4. How many three-digit numbers greater that 600 can be formed from the digits 5, 6, 7, 8, and 9? (Oops … so what formula is applicable now?)
  5. How many numbers greater than 3,000,000 can be formed by arrangements of the digits 1, 2, 2, 3, 6, 6, 6? (More Ooops…)
Having identified some of the difficulties inherent to counting problems, what teaching tip can I propose?
  1. Ask for different ways of solving the problem, slowly discouraging students’ reliance to listing. Thinking in terms of tree diagrams and empty boxes are great help.
  2. Defer introduction of formulas before students can solve the problems like the ones above using the fundamental counting principle. Permutations and combination formulas are only powerful to the extent to which students understand the multiplication principle.
  3. Another pedagogical tip is to ask students to identify what makes a problem similar and different in structure from the problems they previously solved. If they can specify which problem, the better.
  4. As a consequence of tip#3, problems are best given per family with family defined in terms context (e.g., the family of problems given in the example above) and not in terms of similarity in solution structure.

Please add yours. Thanks.

You may want to read my two other posts on combinatorics:

Some useful references: