1
$\begingroup$

I know that for an NxM grid there are "M+N choose N" unique paths to "opposite" {corner to corner} vertices. I would like to know how many "effective unique paths" there are if I discount for repetition along the paths. That is, if a leg is used 3 times, it only contributes 1/3 "uniqueness" each time it is used.

For a 1x1 grid, there are 2 paths, and each leg is 100% unique, so there are 2 "effective unique paths."

For 2X2 grid there are 6 paths (of length 4) but the first and last leg is used 3 times each, and the "middle" segments are used 2ce each or 1ce each, resulting in "3 effective paths"

E.g. the six paths will have the following "discount" applied to each path. P1= 1/3 1/1 1/1 1/3 P2= 1/3 1/2 1/2 1/3 P3= 1/3 1/2 1/2 1/3 P4= 1/3 1/2 1/2 1/3 P5= 1/3 1/2 1/2 1/3 P6= 1/3 1/1 1/1 1/3

This sums to 12, but each fully unique 4 leg paths would sum to 4, so the "effective unique paths" is 12/4 = 3

Is there a generalization for the "number of effective unique paths" as defined above for an NxM {or NxN} grid? { 1x1=2, 2x2=3 implies a pattern :-) }

Also, how is this question properly phrased?

$\endgroup$
1
$\begingroup$

Let $P$ be the set of all paths. Let $E$ be the set of all legs (so for example $|E|$=4 for the 1x1 case and $|E|=12$ for the 2x2 case). Let $\omega(e)$ be the number of times that leg $e$ appears among all the paths - so the weight of $e$ is $\frac{1}{\omega(e)}$.

Now, the number of 'effective unique paths' in an $n\times n$ grid is $$\frac{1}{2n}\sum\limits_{p\in P}\sum\limits_{e\in p}\frac{1}{\omega(e)},$$ where the $\dfrac{1}{2n}$ term comes from the number of legs in any single path.

However, note that in this summation, by definition every leg $e$ appears $\omega(e)$ times among all of the paths in $P$ (also note that $\omega(e)>0$ for every leg $e$). Hence we have

$$\frac{1}{2n}\sum\limits_{p\in P}\sum\limits_{e\in p}\frac{1}{\omega(e)}=\frac{1}{2n}\sum\limits_{e\in E}\omega(e)\frac{1}{\omega(e)}=\frac{1}{2n}\sum\limits_{e\in E}1=\left(\frac{1}{2n}\right)2n\left(n+1\right)=n+1,$$

so the number of 'effective unique paths' is just $n+1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.