Lattice Paths with no more than k consecutive steps I am working on the problem of counting the number of lattice paths (where you may only take steps up or right) from the origin to a point (n, n) with the extra restriction that you can take no more than k consecutive steps in the same direction. When n is 1, the problem is simple as it solves to be a grid with a diagonal of 2s, and 1s surrounding those.
For n > 1 I can't find a simple formula. I have tried adapting the recursive solution for lattice paths where the count for the point (a, b) = (a-1, b) + (a, b-1), but no success. 
What should my next step be?
 A: Assume that you cannot take more than $k$ consecutive steps in the same direction, when going from $(0,0)$ to $(n,n)$ with steps towards east or north. Let a run be a sequence of consecutive steps in the same direction. If we have $a$ runs towards east and $b$ runs towards north, the number of paths fulfilling the given constraints is given by the coefficient of the monomial $x^n y^n$ in
$$\left(x+x^2+\ldots+x^k\right)^a\cdot \left(y+y^2+\ldots+y^k\right)^b. $$
We may also assume, without loss of generality, that the first step is towards east (otherwise, we may consider a reflection with respect to the diagonal of the grid). With such assumption, we may only have $a=b$ or $a=b+1$, so the total number of paths is given by:
$$ 2\cdot[x^{n}y^{n}]\left(\sum_{a\geq 1}\left(x+x^2+\ldots+x^k\right)^a\cdot \left(y+y^2+\ldots+y^k\right)^a\cdot\left(1+y+\ldots+y^k\right)\right) $$
or by:
$$ 2\cdot[x^n y^n]\,\frac{f(x)f(y)+f(x)f(y)^2}{1-f(x)f(y)},\qquad f(z)=z+z^2+\ldots+z^k = z\cdot\frac{z^k-1}{z-1}. $$
The explicit computation in terms of binomial coefficients and $k$-th roots of unity now looks doable, even if not too easy to carry on.
