Paths and chips Combinatorics Consider an integral Cartesian coordinates grid

*

*A valid path from $(0,0)$ to $(n, n)$ (where $n \in \mathbb{N}$) is one where each step is 1 unit in length and is either in the right or the up direction.

*The square $(0,0), (n,0), (n,n)$ and $(0,n)$ contains $n^2$ unit squares. A valid distribution of $n$ chips in these squares is one in which every row and every column contains exactly one chip.

How many ways are there to draw a valid path and validly distribute $n$ chips such that all chips are on the same side of the path drawn?
The answer to the question is $2(2n-1)!!$ we can reach this if we can show that $x_n = (2n-1)x_{n-1}$ for $n>1$. I have tried to prove this using the strategy outlined by Prof. Scott in his answer below but I am not able to make this work. For example consider the following situation:

We start with a know configuration for $n=2$ and try to create two unique distributions by adding a chip to the top left square (2nd row in the figure) and also one to the bottom right one (3rd row in the figure). In each case we end up with the same distribution. So apparently this will not work.
 A: The first step of the path determines whether the chips will be above or below the path, so we might as well assume that it is an up-step and that the chips are below the path, and then double the result.
Each path has one right-step in each column; for $k\in[n]$ let $a_k$ be the number of squares below the right-step in column $k$; $\langle a_1,\ldots,a_n\rangle$ is a non-decreasing $n$-tuple of positive integers less than or equal to $n$, and each such $n$-tuple corresponds to a unique path.
It’s not hard to see that there are $\prod_{k=1}^n\big(a_k-(k-1)\big)$ ways to distribute the chips below the path corresponding to the $n$-tuple $\langle a_1,\ldots,a_n\rangle$. This is $0$ iff $a_k=k-1$ for some $k\in[n]$, which is the case iff the path drops below the diagonal. Thus, we can limit our attention to the $C_n$ paths that do not drop below the diagonal at any point.
If $f(n)$ is the total number of distributions of chips for all paths that do not drop below the diagonal, it’s not hard to calculate by hand that $f(1)=1$, $f(2)=3$, $f(3)=15$, and $f(4)=105$. Either by inspection or by searching OEIS one finds that these are consistent with the conjecture that $f(n)=(2n-1)!!$, OEIS A001147, and in the comments we find that $(2n-1)!!$ is the total weight of all Dyck $n$-paths when each path is weighted with the product of the heights of the terminal points of its up-steps; this sounds rather like the computation in the last paragraph.
The Dyck paths in that comment are up-down Dyck paths starting at $\langle 0,0\rangle$, finishing at $\langle 2n,0\rangle$, never dropping below the $x$-axis, and consisting of up-steps $\langle 1,1\rangle$ and down-steps $\langle 1,-1\rangle$. One of these up-steps corresponds to one of our up-steps, and one of these down-steps corresponds to one of our right-steps. For $n=3$, for instance, the $C_3=5$ Dyck paths are UUUDDD, UUDUDD, UUDDUD, UDUUDD, and UDUDUD, corresponding to our $3$-tuples $\langle 3,3,3\rangle$, $\langle 2,3,3\rangle$, $\langle 2,2,3\rangle$, $\langle 1,3,3\rangle$, and $\langle 1,2,3\rangle$, respectively. (The conversion is mechanical: each D in the Dyck path corresponds to a right-step, and the number of squares below that right-step is the number of up-steps (U) that precede it.) If for $k\in[3]$ we set $b_k=a_k-(k-1)$, we can match up the Dyck paths, the heights of the terminal points of its up-steps, the corresponding $3$-tuples $\langle a_1,a_2,a_3\rangle$, and the $b_k$s:
$$\begin{array}{c|c|c}
\text{Dyck path}&\text{Heights}&\langle a_1,a_2,a_3\rangle&b_1,b_2,b_3\\\hline
\text{UUUDDD}&1,2,3&\langle 3,3,3\rangle&3,2,1\\
\text{UUDUDD}&1,2,2&\langle 2,3,3\rangle&2,2,1\\
\text{UUDDUD}&1,2,1&\langle 2,2,3\rangle&2,1,1\\
\text{UDUUDD}&1,1,2&\langle 1,3,3\rangle&1,2,1\\
\text{UDUDUD}&1,1,1&\langle 1,2,3\rangle&1,1,1
\end{array}$$
Now recall that the Dyck paths correspond to well-formed parenthesis strings, so each up-step has a matching down-step. For instance, UUDUDD corresponds to $(()())$, and the up- and down-steps are properly paired as $\rm{U}_1\rm{U}_2\rm{D}_2\rm{U}_3\rm{D}_3\rm{D}_1$. In the general case suppose that there are $u$ up-steps and $d=k-1$ down-steps preceding the $k$-th down-step of a Dyck path; then $a_k=u$, and $b_k=a_k-(k-1)=u-d$ is the height of the Dyck path at the beginning of the $k$-th down-step. This is precisely the height at the end of the (earlier) matching up-step. Thus, the numbers $b_k$ whose product we want are the same as the heights of the terminal points of the up-steps of the corresponding Dyck path.
Thus, if we’re willing to accept the statement in OEIS, we can conclude that $f(n)=(2n-1)!!$ and hence that the answer to your problem is $2(2n-1)!!$. It would still be nice to have a complete proof, however, and after some thought I came up with an inductive argument that I’ll sketch.
Clearly $f(1)=1$. Suppose that $f(n)=(2n-1)!!$. When we go from an $n\times n$ square of cells to an $(n+1)\times(n+1)$ square, we add $2n+1$ cells forming a new top row and righthand column. If we can show that each of the $f(n)$ satisfactory distributions of chips for the $n\times n$ square somehow produces $2n+1$ satisfactory distribustions for the $(n+1)\times(n+1)$ square, and that all $(2n+1)f(n)$ of the resulting distributions are distinct, we’re done. I’ll sketch such an argument.
Start with some satisfactory distribution $D$ of chips on the $n\times n$ square, and add a chip on one of the $2n+1$ new squares around the top and righthand sides. If you add it at the upper righthand corner, you have a satisfactory distribution on the $(n+1)\times(n+1)$ square. If you add it on the $k$-th cell in the new top row for some $k\le n$, just move each of the old chips in columns $k$ through $n$ one cell to the right; the result is a satisfactory distribution on the $(n+1)\times(n+1)$ square. And if you add it on the $k$ cell from the bottom in the new righthand column for some $k\le n$, just move each of the old chips in rows $k$ through $n$ up one cell; again the result is a satisfactory distribution on the $(n+1)\times(n+1)$ square. Finally, check that every satisfactory distribution on the $(n+1)\times(n+1)$ square can be uniquely obtained in this way.
