counting paths in three-dimensional space  TOPIC_SOLVED

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

counting paths in three-dimensional space

Postby kt5016 on Mon Nov 15, 2010 9:54 am

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

thanks in advance.
kt5016
 
Posts: 1
Joined: Thu Nov 04, 2010 10:29 am

Sponsor

Sponsor
 

Re: counting paths in three-dimensional space  TOPIC_SOLVED

Postby bobbym on Mon Mar 21, 2011 12:15 pm

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.
bobbym
 
Posts: 2
Joined: Mon Mar 21, 2011 11:47 am

Re: counting paths in three-dimensional space

Postby Martingale on Mon Mar 21, 2011 1:30 pm

kt5016 wrote: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? :confused: )

thanks in advance.


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

User avatar
Martingale
 
Posts: 350
Joined: Mon Mar 30, 2009 1:30 pm
Location: USA


Return to Discrete Math