Q) Find the number of pairs of non-intersecting northeastern lattice paths $(p, q)$ so that $p$ goes from $(0,0)$ to $(k,n - k)$ and $q$ goes from $(-1,1)$ to $(k - l, n - k + l)$
My approach: (Before telling my approach I would like to tell that my approach may be wrong or may have some issues, so please if you have any better and efficient approach to solve such problems please discuss that too if possible.)
Basically in their problem it was asked to that $P$ are some paths, $Q$ are some paths. And we have to get all non intersecting paths.
(I am also in dilemma that what non intersection actually is...!)
(The thing which comes in my mind is that when it's said that non intersection, thus I think there should not be any coordinate point common between any of the paths that $P$, $Q$ generate.)
(Please correct me if I am wrong here)
Thus my approach to solve this is going to be something like this:
$$ \text{[Required paths]} = \text{[Total paths]} - \text{[Interacting paths}].$$
(Also tell if this approach is better or should I directly go in searching paths, i.e., $\text{[Required paths]} = \text{[Non-intersecting paths]}$)
So what first I did,
I calculated all the total paths for $P$: $(0,0) \to (k,N-k)$
So to do that I followed the standard procedure for North Eastern paths.
Thus I require to move $k$ times East and then move $N-k$ times North to reach my destination.
So the all possible paths would have $k$ E's and $(N-k)$ N's.
So the total paths are:
$$\binom{N}{k}$$
And now for the total paths $Q$: I have to have $(k-l+1)$ E's and $(N-K+l-1)$ N's.
So the total paths would be:
$$\binom{N}{k-l+1}$$
Now the total paths thus should be:
Product of the above two. (Please tell have I interpreted this thing right?)
$$\binom{N}{k} \cdot \binom{N}{k-l+1} $$
Now yes, this is not all as per my intuition because we haven't taken care about the intersecting paths.
So the main problem lies in how do I get the total intersecting paths.
I have one intuition for this but I am not able to generalize.
I had assumed some random values for $n$, $k$, $l$ and manually solved all cases and had counted all required paths.
So how did I do that?
First of, I went on to calculate the total paths, as per formula.
Then I found out all possible points where the two paths may intersect (which was a too much time consuming process).
Then for $P$, I calculated paths form $(0,0)$ to those intersecting points and from there to the destination. $ \to \# $
Also then for $Q$ I did same, from $(-1,1)$ to intersecting points and from there to destination points. $ \to @ $
Now my claim is $$ \text{[required paths]} = \text{[total paths (i.e. the product)]} - ( \text{#} + \text{@} ) $$
But the problem is the above thing is based in a random example how should I generalize in terms of $n$, $k$.
I am unable to figure that out.
(Also please comment if these approaches I mentioned are right way to proceed to this problem. Or am I committing any mistake?)
Any help in this regard would be much appreciated!
(Please if you can, also suggest some good places to read up about this topic and some practice questions.)