Don’t Count Them Out – Helping Students Successfully Solve Combinatorial Tasks

By Elise Lockwood, Contributing Editor, Oregon State University

Introduction
Solving counting problems is one of my favorite things to do. I love the challenge of making sense of the problem, the work of correctly modeling what I am trying to count, and the fact that I get to reason about astonishingly large numbers. I did not always feel this way about solving counting problems, though. For much of my mathematical career, counting was a mystery – a jumble of poorly understood formulas and equations that just made me miserable. As an undergraduate, I struggled to grasp the difference between order mattering or not mattering, what the respective factorials represented in confusing-looking formulas, and why I should care about how many full houses could be chosen from a deck of cards. My teachers at the time may have shared the sentiment nicely captured by Annin and Lai: “Mathematics teachers are often asked, ‘What is the most difficult topic to teach?’ Our answer is teaching students to count” (2010, p. 403).

At some point during graduate school (thanks to an influential professor who loved counting), I turned the corner and became more interested in understanding counting. Through lots of practice, I began to improve in my ability to solve counting problems. Since that time I have committed my research interests to learning everything I can about undergraduate students’ counting – what they do when they approach counting problems, why they struggle, and how we might help them solve such problems more effectively.

A Model of Students’ Combinatorial Thinking
In this post, I introduce a model of students’ combinatorial thinking that has been helpful for me to make sense of students’ counting activity. I also offer examples that illustrate aspects of the model, and I conclude with specific recommendations for teaching students to solve counting problems.

The model (initially introduced in Lockwood, 2013, and then refined in Lockwood, Swinyard, & Caughman, 2015) consists of three components – formulas/expressions, counting processes, and sets of outcomes – as well as relationships between these components (see Figure 1 below).

Screen Shot 2015-12-05 at 8.57.36 AM

Figure 1 – A Model of Students’ Combinatorial Thinking

The formulas/expressions component refers to mathematical expressions that may be evaluated numerically; these are often considered to be the answer to a counting problem. They may be inherently combinatorial (like a binomial coefficient \({10 \choose 3}\)) or may simply involve numbers and operations (such as \(3^4+2^4)\). Counting processes refer to the actual step-by-step procedures in which someone engages (mentally or physically) as they solve a counting problem. This might involve applying the multiplication principle or implementing a case breakdown. The set of outcomes for a given problem refers to desirable outcomes of that problem – the items that are actually being counted. These outcomes may be encoded in some way (as strings of numbers or letters, for instance), and this component could consist of various ways of encoding and structuring outcomes.

As a simple example to elaborate these components and to highlight the relationships between formulas/expressions, counting processes, and sets of outcomes, consider the following problem: How many 3-letter sequences made from the letters a, b, c, d, e, f can be formed if repetition is not allowed and we must include the letter e? (This problem was introduced in Tucker, 2002).

Before solving the problem, we can consider what the outcomes would look like. They are three-letter sequences (so, abe is different from eab) that contain the letter e where repetition is not allowed (outcomes like abc or aaa are not allowed). To count all such sequences, a three-stage counting process to solve the problem would be first to choose a position in which the e should go (there are 3 options), and then to choose which of the 5 remaining letters (a, b, c, d, f) can go in the next available position, and then to choose which of the 4 remaining letters (the four that were not previously chosen) can go in the last available position. This process yields the formula/expression of \(3 \cdot 5\cdot 4\), which equals 60.

It is important to note that the counting process described above structures the outcomes in a particular way. Specifically, it groups according to where the e is positioned, as the following list of outcomes in Figure 2 suggests:

Screen Shot 2015-12-08 at 10.19.40 AM

Figure 2 – One organization of the set of outcomes

It is worth noting that different counting processes might lead to different structures of the set of outcomes. For example, even if it might not be as elegant a solution, another process might be to organize outcomes according to the first letter. Specifically, we begin with the choice of which letter is first, and if it is a non-e we consider two cases: putting an e in the second position (then cycling through the remaining letters in the third position) and then putting an e in the third position (then cycling through the remaining letters in the second position). If e is the first letter, we cycle through each of the remaining letters for the second and third positions. So, we could consider sequences with different respective first letters, yielding the outcomes being structured as in Figure 3. An expression that reflects this process is \(5 \cdot 2 \cdot 4 + 1\cdot 5 \cdot 4\), which also equals 60. The point of this example is that different ways of structuring or organizing the set of outcomes can reflect different respective counting processes, and, conversely, different counting process can result in different ways of organizing the outcomes.

Screen Shot 2015-12-17 at 1.21.05 PM Screen Shot 2015-12-17 at 1.21.14 PM Screen Shot 2015-12-17 at 1.21.21 PM

Figure 3 – An alternative organization of the set of outcomes

So, why might we care about this model and these components? I contend that there is much value in having students focus on the set of outcomes (Lockwood, 2014), and in particular on thinking about the relationship between counting processes and sets of outcomes. There are a couple of reasons why this relationship is so important to understand. For one thing, if students are not attuned to the set of outcomes (and instead focus primarily on counting processes and formulas/expressions), then rules about which formula to use become harder to parse. Counting can become an exercise in simply manipulating formulas and not clearly understanding what is being counted. Also, certain common pitfalls, like overcounting, are difficult to discover and fix without a solid sense of outcomes and how counting processes relate to those outcomes. As an example of why this relationship is important, consider the following, similar problem involving 3-letter sequences (also found in Tucker, 2002): How many 3-letter sequences made from the letters a, b, c, d, e, f can be formed if we must include the letter e, and repetition of letters IS allowed?

Here, a common counting process is the following: First, place an e in one of three positions. Then, for each placement of the e we can argue that since repetition is allowed, we are now free to put any of the remaining 6 letters in the remaining two positions. This process suggests a formula/expression of \(3 \cdot 6 \cdot 6\). This counting process seems to make sense, and indeed it is a very common response among students. However, this is an incorrect answer, as this process counts some outcomes too many times. To see this, we must carefully consider the outcomes, and in particular how the outcomes are generated and organized by this counting process.

Let us think about the following: Suppose in the first stage of the process, we placed an e in the third position, and then in the remaining stages of selecting one of 6 letters to be in the remaining 2 positions, we chose an e and then an a. This gives a password of eae. However, consider another way of completing this process: we could have first placed an e in the first position, and then in the 6 \(\cdot\) 6 stage we could have selected an a and then an e. This, too, generates the password eae. The ways to complete the process are not in on-to-one correspondence with the number of desirable outcomes, and this process thus causes an overcount.

If a student does not understand that there is a relationship between counting processes and outcomes in this way, how might he or she be aware of when they overcount, let alone be prepared to address and fix that overcount? Counting problems are difficult, and there can be many reasonable-sounding processes. Without grounding that in the set of outcomes, it can be difficult to tell whether (and why) a given process may overcount.

Practical Implications
This issue of overcounting is but one example of why all three components of the model are important, and why we should encourage students to consider sets of outcomes and how they relate to counting processes. In light of this, below I offer some advice about teaching counting problems (particularly to undergraduates, although the same advice might apply to teaching counting at any level).

1) Have students focus on sets of outcomes. The main finding of my research so far is that there is value in having students focus on sets of outcomes. There are a couple of practical ways to do this. First, broadly, teachers should strive to frame counting as an activity of determining the cardinality of a set – specifically, the set of desirable outcomes specified in the counting problem. While this seems rudimentary, we have evidence that students do not always view counting in this way – instead, counting can be a matter of matching formulas, blindly guessing at problem types, etc. For example, when asked about an issue of order in a problem, one of my students once said, “I don’t know, I kind of go off of my gut for it on the ones that don’t specifically say order matters or it doesn’t matter.” Ironically, if students were more attuned to sets of outcomes, I believe this would help them in their pursuits toward finding a given problem type or in applying formulas. Perhaps if we always encouraged students to articulate the nature of what they are counting – by asking questions like What are you trying to count? Are your outcomes more appropriately modeled as sets of things or arrangements of things? – students may be more prone to view counting as an activity involving outcomes. This set-oriented perspective on counting is outlined in Lockwood (2014) and is also mentioned in Hadar & Hadass (1981), Mamona Downs & Downs (2004), and Batanero, Navarro-Pelayo, & Godino (1997).

Second, there is another way in which students might actively engage with outcomes: to have students create partial lists of outcomes. There is mounting evidence that actually engaging in listing activities is a beneficial strategy for students (English, 1991; Halani, 2012), and statistical significance has even been demonstrated (Lockwood & Gibson, in press). Thus, a practical tip would be to have students engage in listing activity.

In some cases, listing can actually offer an answer to a counting problem, and, even more, this solidifies for students what an outcome is. For example, consider the Domino problem, which states: A Domino is a small, thin rectangular tile that has dots on one of its broad faces. That face is split into two halves, and there can be 0 through 6 dots on each of those halves. Suppose you want to make a set of dominos (i.e., one of every possible domino). How many distinguishable dominos would you make for a complete set? On this problem, I have seen students, prior to listing, offer an answer like \(7! \cdot 7!\), which does not make much sense in the context of the problem. By engaging in a problem like this, students can understand the nature of an outcomes, what we want to consider as distinguishable. Also, it is worth noting that partial listing is also helpful, especially on a problem in which the outcomes might be difficult to see/recognize as similar. Partial listing helps because, again, it can orient students to the nature of what is being counting, and often students may extrapolate a more general solution or strategy even from a partial list.

2) Emphasize the relationship between counting processes and sets of outcomes. As students engage in listing, the idea that there is a link between their counting processes and their set of outcomes should be reinforced. As we have noted above, this relationship can be key in helping students detect and deal with issues of order and overcounting, which are two common difficulties that students face. It is also important to note that the expressions and formulas should not necessarily be de-emphasized, because they are important aspects of counting that provide streamlined ways of efficiently solving problems. The issue is that we tend to overemphasize them, and students view them simply as a formula to memorize, not as a generalization and/or formalization of a counting process that makes sense and that actually structures the set of outcomes in some way. Practically, emphasizing this relationship may involve giving students tasks that involve listing, or giving them problems that do not involve a simple application of a formula. The Domino problem and the 3-letter sequences problems are good examples, as is the following Language Book problem (also adapted from Tucker, 2002): You have 5 different Spanish books, 6 different French books, and 4 different Japanese books. In how many ways can you select two books that are not of the same language?

3) Remind students that counting problems are fun and are excellent opportunities for critical thinking. Because there are not clearly prescribed algorithms for solving every problem (unlike solving a page full of integration by parts calculus problems), students can find counting to be frustrating. However, teachers should try to share the perspective that counting is, in fact, an intellectual challenge and can be quite enjoyable. A wonderful example of this is recent videos of students in a middle school math class trying to solve a counting problem (https://www.youtube.com/watch?v=SrWt_XvWLUk). These kids are not stressed about formulas or getting the right answer – they are engaged in critical thinking and problem solving and seem to be having fun doing it!

For undergrads, consider a problem like the following: Suppose you want to put 8 identical white socks and 8 identical red shoes on your pet octopus, who has 8 distinguishable legs. You can do this in any order as long as, for any given leg, the sock goes on before the shoe. In how many different ways can you put shoes and socks on your octopus? If students are given time and space to think about and explore counting as a fun opportunity to solve problems, students may be more comfortable with engaging in outcomes and not simply trying to apply a memorized but not well understood formula.


References:

Annin, S. A., & Lai, K. S. (2010). Common errors in counting problems. Mathematics Teacher, 103(6), 402-409.

Batanero, C., Navarro-Pelayo, V., & Godino, J. (1997). Effect of the implicit combinatorial model on combinatorial reasoning in secondary school pupils. Educational Studies in Mathematics, 32, 181-199.

English, L. D. (1991). Young children’s combinatorics strategies. Educational Studies in Mathematics, 22, 451-47.

Hadar, N., & Hadass, R. (1981). The road to solve combinatorial problems is strewn with pitfalls. Educational Studies in Mathematics, 12, 435-443.

Halani, A. (2012). Students’ ways of thinking about enumerative combinatorics solution sets: The odometer category. In the Electronic Proceedings for the Fifteenth Special Interest Group of the MAA on Research on Undergraduate Mathematics Education. (pp. 59-68) Portland, OR: Portland State University.

Lockwood, E. (2013). A model of students’ combinatorial thinking. Journal of Mathematical Behavior, 32, 251-265. Doi: 10.1016/j.jmathb.2013.02.008.

Lockwood, E. (2014). A set-oriented perspective on solving counting problems. For the Learning of Mathematics, 34(2), 31-37.

Lockwood, E., & Gibson, B. (In press). Combinatorial tasks and outcome listing: Examining productive listing among undergraduate students. To appear in Educational Studies in Mathematics.

Lockwood, E., Swinyard, C. A., & Caughman, J. S. (2015). Patterns, sets of outcomes, and combinatorial justification: Two students’ reinvention of counting formulas. International Journal of Research in Undergraduate Mathematics Education, 1(1), 27-62. Doi: 10.1007/s40753-015-0001-2.

Maher, C. A., Powell, A. B., & Uptegrove, E. B. (Eds.). (2011). Combinatorics and Reasoning: Representing, Justifying, and Building Isomorphisms. New York: Springer.

Mamona-Downs, J. & Downs, M. (2004). Realization of techniques in problem solving: the construction of bijections for enumeration tasks. Educational Studies in Mathematics, 56, 235-253.

Tucker, A. (2002). Applied Combinatorics (4th ed.). New York: John Wiley & Sons.

This entry was posted in Assessment Practices, Classroom Practices, Research and tagged , , , , . Bookmark the permalink.

1 Response to Don’t Count Them Out – Helping Students Successfully Solve Combinatorial Tasks

  1. Christopher McClain says:

    See chapters 6 and 7 of Discrete Mathematics with Ducks by Sarah-Marie Belcastro.

Comments are closed.