Problem: Let $m$ and $n$ be positive integers,
and let $\mathcal R$ be a $2m\times{2n}$ grid of unit squares.
A \emph{domino} is a $1\times2$ or $2\times{1}$ rectangle.
An \emph{up-right} path is a path from the lower-left corner of $\mathcal R$
to the upper-right corner of $\mathcal R$ formed by exactly $2m+2n$ edges of the grid squares.

In terms of $m$ and $n$, find the number of up-right paths that divide $\mathcal R$
into two subsets (possibly empty), each of which can be tiled with dominoes.

Solution: Apply the usual black/white checkerboard coloring.
We define a \emph{staircase} to be the below above an up-right path
(equivalently, a Young diagram rotated $180\dg$).

The proof is composed of two steps.
One is rewriting the ``domino-tileable'' condition to one that is actually usable;
the other is the counting part.

\paragraph{Determining when a staircase can be domino-tileable.}
It turns out the obvious guess is right.

\begin{lemma*}
  A staircase can be tiled with dominoes if and only if
  the number of black and white cells in it is equal.
\end{lemma*}
\begin{proof}
  It's obvious equal black and white cells is necessary; we prove it's sufficient.

  Assume the number of black and white cells is equal.
  The proof is by induction with empty staircases being vacuous.
  We consider the following four cases (which could overlap, pick one arbitrarily if so).
  Note that the latter two cases are just mirrors of the first two.
  \begin{description}
    \ii[Case 1]
    If the rightmost two columns of the staircase have the same height,
    tile those two columns.

    \ii[Case 2]
    If some two consecutive columns of the staircase differ by more than
    two cells in height, say the $(i-1)$\ts{st} and the $i$\ts{th},
    then tile the top two cells in the $i$\ts{th} column and rightwards.

    \ii[Case 3]
    If the bottom two rows of the staircase have the same length,
    tile those two rows.

    \ii[Case 4]
    If some two consecutive rows of the staircase differ by more than
    two cells in length, say the $(j-1)$\ts{st} and the $j$\ts{th},
    then tile the leftmost two cells in the $j$\ts{th} column and below.
  \end{description}
  Needless to say, each induction step preserves that the number of black squares
  equals the number of white squares.
  Hence the remaining cells can then be tiled by the induction hypothesis.
  See the image below for an illustration of all four cases.
  \begin{center}
  \begin{asy}
    pen border = blue + 1.4;
    void draw_staircase(picture pic, string s, int[] heights) {
      int h;
      for (int i=0; i<heights.length; ++i) {
        for (int j=0; j<heights[i]; ++j) {
          draw(pic, shift(i,j)*unitsquare, gray);
        }
        h = heights[i];
        int prev_height = (i>0) ? heights[i-1] : 0;
        draw(pic, (i,prev_height)--(i,h)--(i+1,h), border);
      }
      // h is now the longest height
      int w = heights.length; // max width
      draw(pic, (0,0)--(w,0)--(w,h), border);
      label(pic, s, (w/2,0), dir(-90));
    }
    real eps = 0.2;
    void draw_domino(picture pic, int x, int y, bool vertical) {
      filldraw(pic,
        shift(x,y) * box((eps,eps), vertical ? (1-eps,2-eps) : (2-eps,1-eps)),
        opacity(0.2)+yellow, red);
    }

    picture case1, case2, case3, case4;

    draw_staircase(case1, "Case 1", new int[] {2,3,3,4,4,4});
    draw_domino(case1, 4, 0, false);
    draw_domino(case1, 4, 1, false);
    draw_domino(case1, 4, 2, false);
    draw_domino(case1, 4, 3, false);

    draw_staircase(case2, "Case 2", new int[] {1,1,3,4,4,5});
    draw_domino(case2, 5, 3, true);
    draw_domino(case2, 4, 2, true);
    draw_domino(case2, 3, 2, true);
    draw_domino(case2, 2, 1, true);

    draw_staircase(case3, "Case 2", new int[] {2,2,3,4,4,5});
    draw_domino(case3, 0, 0, true);
    draw_domino(case3, 1, 0, true);
    draw_domino(case3, 2, 0, true);
    draw_domino(case3, 3, 0, true);
    draw_domino(case3, 4, 0, true);
    draw_domino(case3, 5, 0, true);

    draw_staircase(case4, "Case 4", new int[] {1,2,3,3,4,5});
    draw_domino(case4, 0, 0, false);
    draw_domino(case4, 1, 1, false);
    draw_domino(case4, 2, 2, false);

    add(shift(0,7)*case1);
    add(shift(8,7)*case2);
    add(shift(0,0)*case3);
    add(shift(8,0)*case4);
  \end{asy}
  \end{center}

  I claim that at least one of these four cases must apply unless the staircase is empty.
  This could only occur if the heights of the staircase are $1,2,\dots,k$ in that order.
  However, in that case the number of black cells and white cells
  are obviously not equal (unless $k=0$), so this can never occur.
  This completes the induction.
\end{proof}

\paragraph{Counting.}
Back to the main problem.
The point is that we need to find the number of up-right paths
for which the two resulting regions have equal numbers of black and white squares;
call such paths \emph{balanced}.
Since the overall $2m \times 2n$ grid has $2mn$ black and $2mn$ white squares,
it's sufficient for just the bottom-right staircase to have equal black and white cells.

Then in general, an up-right path is characterized by integer sequences
\[ 0 \le h_1 \le h_2 \le \dots \le h_{2n} \le 2m \]
corresponding to the heights of the staircase.
\begin{claim*}
  The $(h_i)$ correspond to a balanced up-right path if and only if
  $\{ i : h_i \equiv 1 \pmod 2\}$ has an equal number of even and odd indices.
\end{claim*}
\begin{proof}
  WLOG let's fix our coloring so that the bottom-left square is black.
  Then in the $i$\ts{th} column, for $i = 1, \dots, 2n$, has
  (i) one more black square than white if $h_i$ is odd and $i \equiv 1 \pmod 2$;
  (ii) one more white square than black if $h_i$ is odd and $i \equiv 0 \pmod 2$;
  (iii) equal black and white squares if $h_i$ is even.
  The conclusion follows immediately.
\end{proof}

The trick is to instead define
\[ t_i \coloneq h_i + i. \]
That is, we will instead describe the up-right paths by integer sequences $t_i$ with
\[ 1 \le t_1 < t_2 < \dots < t_{2n} \le 2n+2m. \]
\begin{claim*}
  The $(t_i)$ correspond to a balanced up-right path if and only if
  the set $\{t_1, \dots, t_{2n}\}$ has an equal number of even and odd elements.
\end{claim*}
\begin{proof}
  Translating the four cases between the two notations gives the following table:
  \[
    \begin{array}{c|cc}
      & i \text{ even} & i \text{ odd} \\ \hline
      h_i \equiv 1 \pmod 2 & a & b \\
      h_i \equiv 0 \pmod 2 & 2n-a & 2n-b
    \end{array}
    \iff
     \begin{array}{c|cc}
      & i \text{ even} & i \text{ odd} \\ \hline
      t_i \equiv 1 \pmod 2 & a & 2n-b \\
      t_i \equiv 0 \pmod 2 & 2n-a & b.
    \end{array}
  \]
  Then we have
  \[ \text{balanced} \iff a=b \iff a+(2n-b) = (2n-a)+b
    \iff \#\{\text{odd } t_i\} = \#\{\text{even } t_i\} \]
  as desired.
\end{proof}

Hence we must count the number of $2m$-element subsets of $\{1, 2, \dots, 2n+2m\}$
with $m$ even and $m$ odd terms.
Since the even and odd terms can be chosen separately,
this gives an answer of $\binom{n+m}{m}^2$.