White Dot, Black Dot

The first key realization is that there must be the same number of horizontal segments in the top row as in the bottom row . Otherwise, after the dots are paired off vertically and diagonally, there will be some number of dots left in one row, which either can be connected to form the missing horizontal segments or are un-connectable.

The second key realization is that given a fixed number of horizontal segments in each row, for each possible arrangement of horizontal segments, there is exactly one way to draw the remaining segments . To see why this is, let's take this combination of horizontal segments with a fixed 3 horizontal segments in both the top and bottom rows:

Consider the leftmost unconnected dot in the arrangement, which is the white dot in the bottom row. The only dot that this white dot can connect to is the leftmost black dot on the top row, because any other connection will block the other dots from forming horizontal or diagonal segments. Thus, we must do this:

Then, we take the next leftmost dot of the arrangement and repeat the same process over and over. We end up with this arrangement:

Note that the segments we drew were forced; we could not pair up the dots in any other way without introducing more horizontal segments or leaving some dots unconnected. Thus, for each combination of a fixed number of horizontal line segments in each row, there is only one way to connect the other dots.

Combining our observations, to count the total number of ways to connect the dots, we count the number of ways to draw a fixed number $h$ of horizontal segments in one row, square that number, and finally sum those squared terms over all possible values of $h.$

Since we have 10 dots in a row, $0 \leq h \leq 5.$ The cases of $h = 0$ and $h = 5$ are easy; there's only one way to connect the remaining dots for both cases, so the number of ways to draw the segments for each case is $1^2.$ The case of $h = 1$ is also straightforward: there are 9 ways to draw exactly one horizontal segment in one row, so there's $9^2$ ways to draw the rest of the segments.

Suppose $2 \leq h \leq 4.$ If we draw the horizontal segments from left to right, we see that drawing $h$ horizontal segments is the same as choosing $h$ starting points for the segments. There are only 9 possible starting points to draw each segment, which are the first 9 dots in the row.

Now, we will make a bijection between choosing the starting points and a stars and bars argument. Because each dot can only be connected to one other dot, the starting points must be spaced at least one apart from each other. Let $a_1, a_2, \dots, a_{h + 1}$ be nonnegative integers such that $a_i$ represents the number of dots between the $(i - 1)$ th starting point and the $i$ th starting point. (Points 0 and $h + 1$ are the beginning and end of the row, respectively.) Since starting points must be spaced at least one apart, we have $a_2, a_3, \dots, a_h \geq 1.$ Because $h$ of the dots must be starting points, the sum of all the gaps must be equal to $9 - h$ :

$a_1 + a_2 + a_3 + \cdots + a_{h + 1} = 9 - h.$

Let $a'_i = a_i - 1$ for $2 \leq i \leq h.$ We can rewrite the equation above as

$\begin{aligned} a_1 + (a'_2 + 1) + (a'_3 + 1) + \cdots + a_{h + 1} &= 9 - h \\ a_1 + a'_2 + a'_3 + \cdots + a_{h + 1} + (h - 1) &= 9 - h \\ a_1 + a'_2 + a'_3 + \cdots + a_{h + 1} &= 10 - 2h. \end{aligned}$

Each of the terms is nonnegative, so by stars and bars, the number of ways to assign values to each is $\dbinom{(10 - 2h) + h}{h} = \dbinom{10 - h}{h}.$ Because each variable represented a gap between starting points, $\dbinom{10 - h}{h}$ is also the number of ways to choose starting points such that each starting point is at least one dot apart i.e. the number of ways to draw $h$ horizontal segments in a row. Squaring this gives $\dbinom{10 - h}{h}^2$ ways to draw the remaining segments.

Finally, the total number of ways to draw the segments under the given rules is

$\begin{aligned} 1^2 + 1^2 + 9^2 + \displaystyle \sum_{h = 2}^4 \dbinom{10 - h}{h}^2 &= 1 + 1 + 81 + \dbinom{8}{2}^2 + \dbinom{7}{3}^2 + \dbinom{6}{4}^2 \\ &= 83 + 28^2 + 35^2 + 15^2 \\ &= \boxed{2317}. \end{aligned}$

Note that the final sum is equivalent to $\displaystyle \sum_{h = 0}^5 \dbinom{10 - h}{h}^2.$ In general, the number of ways to draw $n$ segments between a grid of $2 \times n$ dots is $\displaystyle \sum_{k = 0}^{\left \lfloor \frac{n}{2} \right \rfloor} \dbinom{n - k}{k}^2.$

Top keep the solution general, let $N = 10$ .

I started my solution similar to that of Steven: In each row, we can freely choose connected pairs of neighboring dots, provided that we choose the same number of pairs in the top row and the bottom row. The remaining dots may now be connected across the rows by a vertical or diagonal segment.

To count the number of ways to choose the neighboring dots, think of the individual dots as "stars" and the chosen pairs as "bars". It is generally known that $s$ stars and $b$ bars may be placed in $\binom {s + b}b$ ways. Applying this here, if $b = n$ is the number of horizontal pairs in each row, then there are $s = N - 2n$ individual dots left, so that $\text{there are}\ \binom{N - n}n\ \text{ways to select}\ n\ \text{horizontal pairs in each row}.$ Since we must choose this configuration independently in each of the rows, we take the square; then sum over the possible number of horizontal pairs: $A(N) = \sum_{n = 0}^{\lfloor N/2\rfloor} {\binom{N - n}n}^2.$

Substituting $A(10)$ we obtain $A(10) = {\binom{10}0}^2 + {\binom 9 1 }^2 + {\binom 8 2}^2 + {\binom 7 3}^2 + {\binom 6 4}^2 + {\binom 5 5}^2 = 1^2 + 9^2 + 28^2 + 35^2 + 15^2 + 1^2 = \boxed{2317}.$

---

Note that the sequence $A(N)$ is known as the Whitney numbers of the second kind .

Note also that the calculation can be illustrated in Pascal's Triangle. Square the circled numbers and add: