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.)
Your question is equivalent to finding the number of ways to tile a $9$-by-$5$ rectangle with pentominoes.
Unfortunately there is no easy way to compute this by hand. (There might be a way to brute-force this using a system of recurrence relations, but I suspect this might take days and weeks to solve.) Instead, I found that both OEIS and this paper use a computer algorithm to compute that the answer is $13205354$.