counting paths in three-dimensional space

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.
kt5016
Posts: 1
Joined: Thu Nov 04, 2010 10:29 am
Contact:

counting paths in three-dimensional space

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? )

bobbym
Posts: 2
Joined: Mon Mar 21, 2011 11:47 am
Contact:

Re: counting paths in three-dimensional space

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

$\Large {3m \choose m } { 2m \choose m } {m \choose m } = {3m \choose m} {2m \choose m}= \frac{(3m!)}{(m!)^3}$

So it least that part is correct.

Martingale
Posts: 333
Joined: Mon Mar 30, 2009 1:30 pm
Location: USA
Contact:

Re: counting paths in three-dimensional space

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? )

${a+b+c \choose a,b,c}=\frac{(a+b+c)!}{a!b!c!}$