Counting Lattice Paths with Pfaffian This problem comes from Stanley's Enumerative Combinatorics Volume 1 (Problem 37, page 265). 
The problem statement is quite long, so I have added an image, but as a short synopsis the problem asks to show that the number of paths from $(2a_1, 0)$ to $(2a_2, 0)$ ... to $2a_n, 0)$ with steps that are either $(1, 1)$ or $(1, -1)$ and where the path never falls below the x-axis is equal to Pfaffian(A) where $A = C(a_j - a_i)$. ($C(n)$ denotes the $n$th Catalan number). (Note: This material comes from section 2.7 of the book).
I have been thinking about this problem for about a week now, but I can't seem to get anywhere.
I would appreciate any advice.

 A: Let $\mathscr{L}$ and $\overline{\mathscr{L}}$ denote the set of n-paths and the set of non-intersecting n-paths respectively (with the given lattice steps and end points of course). Like in the proof of Theorem 2.7.1. (the Lindström-Gessel-Viennot Lemma) there exists a sign-reversing involution
$$ \mathscr{L} \setminus \overline{\mathscr{L}} \xrightarrow{\sim} \mathscr{L} \setminus \overline{\mathscr{L}} \tag{1} $$
which can be obtained by switching at the first place where two intersecting paths meet.
Now let
$$ \Phi[\mathscr{G}] = \sum_{\mathbf{L} \in \mathscr{G}} \operatorname{sgn}(\mathbf{L}) $$
be the signed sum of the lattice paths in the set $\mathscr{G}$. Here if $\mathbf{L}$ connects $a_{i_k}$ to $a_{j_k}$ for $k = 1,\dots,n$ then
$$ \operatorname{sgn}(\mathbf{L}) = \operatorname{sgn}\begin{pmatrix} 1 & 2 & \cdots & 2n-1 & 2n \\ i_1 & j_1 & \cdots & i_n & j_n \end{pmatrix}. $$
Observe that $\Phi[\overline{\mathscr{L}}]$ counts non-intersecting paths (without signs) because for non intersecting paths, the signs are all positive. This is because if you have a pair of paths, one from $a_i$ to $a_j$ and one from $a_{i'}$ to $a_{j'}$ then we either have $i < j < i' < j'$ or $i < i' < j' < j$, we can't interleave the paths and have $i < i' < j < j'$; they would have to cross. Now part of the permutation we obtain will look like
$$ w = \begin{pmatrix} 1 & 2 & 3 & 4 \\ i & j & i' & j' \end{pmatrix} $$
(or possibly the second row is $i',j',i,j$). In either case, we see that the number of inversions corresponding to these two pairs is even. If $i < j < i' < j'$ there are no inversions, if $i < i' < j' < j$ there are two inversions: $w(2) > w(3)$ and $w(2) > w(4)$. If the bottom row is $i',j',i,j$ instead, that permutation has the same sign because we made an even number of interchanges. Therefore all the non-intersecting paths have a positive sign.
Now, the invoultion, $(1)$, says that
$$ \Phi[\mathscr{L}] = \Phi[\overline{\mathscr{L}}] + \Phi[\mathscr{L}\setminus\overline{\mathscr{L}}] = \Phi[\overline{\mathscr{L}}] $$
since $\Phi[\mathscr{L}\setminus\overline{\mathscr{L}}] = 0$.
On the other hand, $\Phi[\mathscr{L}]$ is just $\operatorname{Pf}(A)$ because, by the product lemma, the number of paths connecting $a_{i_k}$ to $a_{j_k}$ for $k = 1,\dots,n$ is the product of the number of paths connecting $a_{i_1}$ to $a_{j_1}$ times the number of paths connecting $a_{i_2}$ to $a_{j_2}$ times etc. times the number of paths connecting $a_{i_n}$ to $a_{j_n}$.
