Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
To confirm, do you still allow moves of (0,1) and (1,0) in addition to (1,n)? –  Ross Millikan Oct 5 '11 at 14:00
    
@Ross: no, (0, 1) and (1, 0) are not allowed. We can only jump in steps of (1, n) –  user952949 Oct 5 '11 at 14:02
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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