Below is an idea to express the answer in terms of sum of Catalan numbers.

Construct a size-(2n) sequence for P1 such that the i-th term is 1 if P1 is moving upward at the i-th step, and 0 otherwise. Similarly for P2. For example, when n=4, and P1 is RRURUURU, the sequence is (0,0,1,0,1,1,0,1); if P2 is UUURRURR, the sequence is (1,1,1,0,0,1,0,0).

The consider the sequence of P2 minus the sequence of P1. For example, in the last paragraph, we get (1,1,1,0,0,1,0,0) - (0,0,1,0,1,1,0,1) = (1,1,0,0,-1,0,0,-1).

The difference sequence has some properties:

1) Each term is either 1, 0 or -1.

2) The partial sum is never negative.

Hence, we can obtain the number answer by

a) choosing a Catalan sequence of size k (where n>=k>=0)

b) in the difference sequence choose 2k coordinates for the Catalan sequence

c) in the other coodinates, put zero's

d) the k one's must correspond to k up's in the sequence of P2. However, there are some other (n-k) ups of P2, which is "hidden" at the zero's of the difference sequence (like the third coordinate in the example I mention above). So we need to choose (n-k) zero's corresponding to the up's in the sequence of P2

This give the answer

$sum_{k=0}^n C(2n,2k) C_k C(2n-2k,n-k) = \sum_{k=0}^n (2n)! / (2k)! / ((n-k)!)^2 * C_k,$

where $C_k$ is the k-th Catalan number, and $C(a,b)$ is "a chooses b".

The sum may be simplified using exponential generating function, but I am uncertain at this moment. Any comment?