Consider a lattice path where one starts at $(0,0)$ and can move only right or up in integer steps. The total number of steps made is $4$, but the maximum steps in one direction $3$. How many paths exist?
I have two different ideas but I'm not sure which (if either) is correct. The first: $$\frac{n!}{n-k!}=\frac{6!}{2!}$$ where $n$ is the number of different movement options ($3$ up and $3$ right) and $k$ is the number of spaces ($4$). From here there are three different scenarios:
$$(right, up): (3,1),(2,2),(1,3).$$
Considering each of these, the number of paths is given by: $$\frac{6!}{2!}\sum_{i=1}^{3}\frac{1}{i!(k-i)!}=\frac{6!}{2!}(\frac{1}{3}+\frac{1}{4})=\frac{6!\cdot7}{2!\cdot12}=\frac{7!}{4!}=210$$ which seems very high. Alternatively: $$\sum_{i=1}^{3}\frac{4!}{i!(k-i)!}=14$$ which considers 4 different arrangements of each scenario (I think).
I think the second method is correct, but I don't really understand where my thinking fails in the first method. If anyone could provide intuition as to why it is wrong, that would be great.
If you start with $(0,0)$ and in each step add $(1,0)$ or $(0,1)$, going $4$ steps in total, there are $2^4=16$ possible paths. If you forbid path's where the $x$ or $y$ coordinate ends up above $3$, you have to subtract the two paths going either all 4 steps up or all 4 steps right. In total you have $16-2=14$ paths satisfying your condition.
In general, the number of paths ending in $(x,y)$ is given by $\binom{x+y}{x} = \binom{x+y}{y}$ since you are going $x+y$ steps and have to choose which of them are up and which are right. So the $16$ pathes split as $$ \binom{0+4}{0} + \binom{1+3}{1} + \binom{2+2}{2} + \binom{3+1}{3} + \binom{4+0}{4} =1+4+6+4+1. $$ So if you want to make $n$ steps in total, only allowing at most $k\le n$ in each direction you get $$ \sum_{i=n-k}^{k} \binom{n}{i}. $$