A state comprises 45 counties arranged as 5 rows, running east and west, of 9 counties each, the nine colums of 5 running north and south. They're connected horizontally and vertically, i.e. immediately neighboring counties are only those immediately to the north and south, or east and west of each other.
The state is to be partitioned into 9 constituencies of 5 counties each. The number of ways to do that would be easy to find but for this constraint: each constituency must be contiguous, or "connected" if you like.
How can it be done with that constraint?
(I find it alleged that this is a crude approximation to an actual situation that occurred more than two centuries ago, but I think the actual combinatorial problem was posed far more recently. I actually heard this from someone wondering how the outcomes of some distant past elections might have been different if those boundaries had been drawn differently.)