TL;DR: In simple combinatorics problems, is there a systematic way to detect overcounting before computing the counts and comparing them? Is it simple enough to be taught to undergrads:
At my university, we teach "Finite", a terminal math course for non-majors. It's very popular --- "popular" --- since it's required for gen ed and the business school. Roughly a quarter of the course is devoted to simple combinatorics. Here's a standard type of question:
You have a standard deck of playing cards (fifty two cards, four suits of thirteen cards each). You draw a hand of five cards. How many ways are there of drawing at least one card from each suit?
The correct answer is $C(4,1)C(13,2)C(13,1)^3$: First choose one suit to draw two cards from, then choose two cards from that suit, then choose one card from each of the remaining three suits.
However, if a student hasn't set the problem up quite correctly but still groks the basic idea of coming up with a method for selecting the hand and counting from it, they might think: First I'm going to draw one from each suit and then draw one from the remaining cards: $C(13,1)^4C(48,1).$
Problem: The second method double-counts every outcome.
Here's another standard sort of question:
You have five pens, four erasers, and three pencils. You draw three of them. How many ways are there of drawing at least two erasers?
The correct answer is $C(4,2)C(8,1) + C(4,3)$, since you can either draw two erasers and one other thing, or you can draw three erasers. However, a student might think: I'll draw two erasers, and then I'll draw one of the remaining ten things: $C(4,2)C(10,1)$.
Problem: The second method overcounts by eight.
These two overcounts are typical student mistakes. They're very subtle. They're of two different types -- one is a multiplicative overcount and another is an additive overcount. And I can't figure out how to quickly tell whether a method (e.g. "draw one from each suit, then draw a fifth card") will lead to an overcount. The best I can come up with is "do the problem correctly and compare the answer with the number they got."
What I'd like to do is figure out how to tell whether a method for finding an answer is an overcount without actually having to compute the number it gives and compare that to the correct count. I thought about this for a while, talked with another teacher, and we couldn't figure out how to teach students to identify and correct these mistakes. Of course, the first priority is teaching students to correctly break down the problem, but after that, it wasn't clear to us how best to instruct students to be aware of and correct these subtle counting errors.
Question: Is there a systematic way to catch and correct overcounting errors in simple combinatorics?
