counting problem

A counting problem asks how many solutions there are, not whether one exists or what one looks like. "How many ways can you make change for a dollar?" "How many paths run from the top-left to the bottom-right of this grid?" "How many ways can these eight queens be placed so none attacks another?" The output is a number — a tally of all the valid answers — and that number can be enormous even when each individual solution is easy to describe.

Formally, a counting problem takes the set of acceptable solutions defined by some search problem and asks for its size. So where the decision version asks "is there at least one solution?" and the search version asks "give me one solution," the counting version asks "exactly how many solutions are there?" For a simple example, counting the subsets of an n-element set has the clean answer 2^n; counting the ways to choose 2 items from 5 has the answer 10. These small cases have neat formulas, but in general counting can be much harder than finding: you might be able to produce one valid coloring of a map quickly yet have no fast way to count all of them.

Counting matters wherever probabilities, averages, or totals are at stake — the number of favourable outcomes over the number of possible outcomes is a count divided by a count. It is also a sharp lesson in how problems relate: counting is at least as hard as deciding (if you know the count, you know whether it is zero, which answers the decision problem), and there are problems where deciding is easy but counting is believed to be intractable. So "just count them" is rarely as innocent as it sounds; the tally hides real computational difficulty.