counting paths in three-dimensional space

[kt5016]

i encountered a problem on counting.

we have a 3 dimensional space. starting from (0,0,0), we need to go to (a,b,c) where a, b and c are positive integers by adding (1,0,0), (0,1,0) or (0,0,1). how many different paths are there?

using a tree diagram, i tried to find out the number of paths of a=1,b=1,c=1 and a=1,b=2,c=1. 6 and 12 respectively.

from those, i wrote an equation which do not look alright.

total number of moves n = a + b + c
number of possible paths = nCa * (n-a)Cb * (n-a-b)Cc

what is wrong for my equation? (or is it actually correct? )

thanks in advance.

[bobbym]

Hi kt5016;

Your formula is indeed correct for (0,0,0) to (m,m,m). It exactly coincides with the
number of paths of length 3n in an m x m x m grid from (0,0,0) to (m,m,m) and is called De Bruijn's s(3,n). Your fomula for (0,0,0) to (m,m,m) becomes



So it least that part is correct.

[Martingale]

i encountered a problem on counting.

we have a 3 dimensional space. starting from (0,0,0), we need to go to (a,b,c) where a, b and c are positive integers by adding (1,0,0), (0,1,0) or (0,0,1). how many different paths are there?

using a tree diagram, i tried to find out the number of paths of a=1,b=1,c=1 and a=1,b=2,c=1. 6 and 12 respectively.

from those, i wrote an equation which do not look alright.

total number of moves n = a + b + c
number of possible paths = nCa * (n-a)Cb * (n-a-b)Cc

what is wrong for my equation? (or is it actually correct? )

thanks in advance.

this formula is correct...though I would write it in the usual multinomial coefficient form....