Combinatorics Question with bridges and inability to cross over each other

Question

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?

Answer 1

For each village on one side, consider the set of villages on the other side it directly connects to.

Label the villages on one side from $v_1$ to $v_{15}$ and the other side from $u_1$ to $u_{20}$.

Clearly, the highest numbered village $v_i$ connects to equal to the lowest numbered village $v_{i+1}$ connects to. If it is more, the two bridges will intersect. Hence it is less than or equal. If it is less, then if $v_i$ connects to $u_j$ and $v_{i+1}$ connects to $u_k$ with $j<k$, $u_k$ is not indirectly connected to $v_i$.

If a village $v_i$ directly connects to $u_a$ and $u_b$, it is directly connected to $u_c$ where $a\leq c\leq b$. This can be obtained from the fact that if $u_c$ is connected to something else, then it causes an intersection of bridges, hence, $u_c$ would connect to $v_i$.

Hence, this "partitions" the villages on one side into the villages of the other side. Instead of "partitioning" the villages, we look at the bridges. Each bridge is associated to exactly one village $v_i$. We partition all $20+15-1$ bridges into $15$ villages. By stars and bars or otherwise, we obtain the answer of ${(20-1)+(15-1)\choose(15-1)}$.

Answer 2

(The following is a rephrasing of @Element118 's answer. I hope it is easier to understand.)

Let $a_i$ $(1\leq i\leq m)$ be the villages on the north rim, and $b_j$ $(1\leq j\leq n)$ be the villages on the south rim. An admissible configuration of bridges is a bipartite tree on the vertex set $$V:=\{a_1,\ldots, a_m\>, \> b_1,\ldots, b_n\}\ ,$$ hence has $m+n-1$ edges. We start by drawing the $m+n-1$ bridges: $$| \quad | \quad | \quad | \quad \cdots \quad | \quad | \quad |$$ Each of these bridges has a north bridgehead which is one of the $a_i$, and each $a_i$ is the north bridgehead of at least one bridge. We therefore choose $m-1$ from the $m+n-2$ slots between the bridges in order to encode which bridge has its north bridgehead at $a_1$, $a_2$, $\ldots$, $a_m$ in succession. Put a separating $*$ in each of the chosen slots. The result looks as follows: $$| \quad | \quad | \> *\> | \quad |\>*\>|\quad\cdots \quad | \quad | \>*\>|$$ There are $${m+n-2\choose m-1}\tag{1}$$ possible choices for the $*$ in all. The resulting architectural configuration is completely determined in this way by stipulating that bridges separated by a $*$ should have their south bridgehead at the same vertex $b_j$, because otherwise the resulting graph would be disconnected. The resulting number of southern bridgeheads is then given by $m+n-1-(m-1)=n$, as it should be.

The total number of admissible configurations is therefore given by $(1)$, which for $m=15$ and $n=20$ comes to $${33\choose14}=818\,809\,200\ .$$