Number of ways in a 3D lattice

[nickek]

Hi!
If I have points A and B in a lattice in the plane, and the closest path between them is n + m steps (for example 4 steps upwards and 5 steps to the right), there are C(9,(5-4)) = 9 combinations of paths between them. I have to choose the 4 ways upwards (or the 5 ways to the right) of the 9 total (there are just 2 possibilities in the node, so when I choose 1 of them I'm done).

But if the lattice is in the 3D space, and I have 3 choices in each node, how can I solve the number of paths in this case? E.g k + m + n = 3 steps inwards, 4 steps upwards and 5 steps tho the right. And what if we have a lattice in any dimension?

Thanks!
Nick

 

[andrewkirk]

Are you sure about the 2D case? My reasoning is that, out of the n+m steps, we have to choose the m that are upwards, so the number of paths is C(n+m,m), which is more than n+m if m>1.

My approach leads to a natural extension to the formula for the number of paths in any number of dimensions. The answer will be a product of Combinations.

 

[nickek]

Are you sure about the 2D case? My reasoning is that, out of the n+m steps, we have to choose the m that are upwards, so the number of paths is C(n+m,m), which is more than n+m if m>1.

My approach leads to a natural extension to the formula for the number of paths in any number of dimensions. The answer will be a product of Combinations.

Thank you. Yes, the number of paths should be C(n+m,m).

I will think more about the extension.

Tanks again!

 

[imranq]

Check out this video: https://www.khanacademy.org/math/re...rain-teasers/v/3-d-path-counting-brain-teaser

Look at trinomial functions for general case

 

[andrewkirk]

I will think more about the extension.

Let me know how you go. I'm still working on calibrating my hints to steer a good path between too broad (a dead giveaway) and too narrow (not much help). Sometimes that challenge seems harder than solving the problem itself!

 

[nickek]

Check out this video: https://www.khanacademy.org/math/re...rain-teasers/v/3-d-path-counting-brain-teaser

Look at trinomial functions for general case

Great! Actually what I looked for.