0
$\begingroup$

You know, how we can have lattice paths, where we can move either one block north, or one block east, and we have the find all the possible ways of reaching the point (x.y) from (0,0).

That is $\binom{x+y}{x}$ paths we can have.

But what if, instead of only being able to move one block at a time, we can move move (1, n) number of blocks at a time, where n is any positive integer (and in the north direction). How many ways are there of going to a point (x, y) with this?

  • 0
    @Ross: no, (0, 1) and (1, 0) are not allowed. We can only jump in steps of (1, n)2011-10-05

1 Answers 1

3

Given that all steps are of the form $(1,n)$, you need to have exactly $x$ steps. So you are looking at compositions of $y$ in $x$ parts. If you imagine $y$ sticks in a row, you need to select $x-1$ places of the $y-1$ available to break the row, so there are $\binom{y-1}{x-1}$ of them