Combinatorics was never easyDiscrete Mathematics Level 4
Several small villages are situated on the banks of a straight river. On one side, there are 20 villages in a row, and on the other there are 15 villages in a row. I would like to build bridges, each of which connects a village on the one side with a village on the other side. The bridges must be straight, must not cross, and it should be possible to get from any village to any other village using only those bridges (and not any roads that might exist between villages on the same side of the river). How many different ways are there to build the bridges?