2
$\begingroup$

Consider lattice paths from $(0,0)$ to $(2n,2n)$ with steps $N=(0,1)$ and $E=(1,0)$ avoiding the points $(2i-1,2i-1)$ for all $1\leq i\leq n$. There are Catalan many $C_{2n}=\frac1{2n+1}\binom{4n}{2n}$ distinct paths of this sort (see, for example, Stanley's EC2, Chapter 6).

A natural variation is: enumerate lattice paths (only north and east steps) from $(0,0)$ to $(2n-1,2n-1)$ avoiding the points $(2i,2i)$ for all $1\leq i\leq n-1$. One may engage the method of inclusion-exclusion to compute these numbers. The simplified form becomes $$2^{2n-1}C_{n-1}.$$

QUESTION. Is there a way to derive the latter counting assuming the former?

Improve this question
$\endgroup$
2
  • $\begingroup$ Aren't the answers quite different for expecting this? On the other hand, the proofs via recurrence are almost identical. $\endgroup$
    – Fedor Petrov
    Commented Jun 12, 2023 at 5:27
  • $\begingroup$ @FedorPetrov: I understand what you are saying. One possibility is suggested by: while looking for paths from $(0,0)$ to $(2n+1,2n+1)$ (avoiding "even holes"), part of those would be those passing through $(1,1)$ and so one is counting paths from $(1,1)$ to $(2n+1,2n+1)$ avoiding "even holes" but these amount to paths from $(0,0)$ to $(2n,2n)$ avoiding "odd holes" - exactly the Catalan types. Of course, I don't mean that is all there is to it. $\endgroup$
    – T. Amdeberhan
    Commented Jun 12, 2023 at 13:49

0

Reset to default

You must log in to answer this question.