Re: Re: Re: Combinatorica questions!!!
- To: mathgroup at smc.vnet.net
- Subject: [mg20777] Re: [mg20733] Re: [mg20645] Re: [mg20499] Combinatorica questions!!!
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Thu, 11 Nov 1999 00:22:50 -0500
- Sender: owner-wri-mathgroup at wolfram.com
In fact, the general formula for d dimensions is Multinomial[n,n,...,n] (d n's), and this formula can also be written (d*n)! / (n!)^d. This formula follows directly from recognizing that the generating function (x1 + x2 + ... + xd)^n for such paths is the same as the generating function for the multinomial coefficients. Rob Pratt Department of Operations Research The University of North Carolina at Chapel Hill rpratt at email.unc.edu http://www.unc.edu/~rpratt/ On Wed, 10 Nov 1999, Tomas Garza wrote: > Kew Joinery [kewjoi at hixnet.co.za] wrote: > > > The case has been solved perfectly well. Can you do so for > > slightly different > > task: > > Same conditions, but for 3 dimensional 8x8x8 chessboard (cube). > > Imagine that > > the rook can move not only on the surface but inside the cube too. > > To make it clear I will denote the start position of the rook > > {0,0,0}. The target > > is final position {7,7,7} which is the farthest opposite point. > > The rook can move > > as usual (not diagonally), the only constraint is you can move the rook in > > increasing order of each coordinate. > > Example for allowable move: > > Say from {0,0,0} to {0,6,0} but not {0,6,6}, > > Say from {4,3,5} to {4,7,5} but not {4,1,5}. > > In other words: the change of only one coordinate at a time > > equals one move of > > the rook, and the change could be in increasing order of each coordinate! > > *** The task is how many different ways (walks) does a castle > > have to reach from > > position {0,0,0} to position {7,7,7}? > > (**Is there a general formula or generating function for higher > > dimension? ) > > (Note: some people could find the question not relevant to the > > group, but this is > > pure mathematics and this is just the beginning of the difficult > > questions and > > answers normally are available only to research people as usual, > > so everyone > > could learn something positive). > > In a two-dimensional chessboard (8x8 cube) each admissible path of the rook > which leads from the initial position (lower left) to the final position > (upper right) is of the form {z1,z2,...,z14}, where each zi is one of the > two symbols r,u, (i.e., one step to the right or one step upwards), and > there must be precisely 7 u's and 7 r's. The number of paths is then equal > to the number of choices for the placement of the r's in the 14 available > positions. This is equal to Binomial[14, 7] = 3432, as proposed by several > contributors in this group. > If the problem is now extended to a three-dimensional chessboard (8x8x8), > then, for each solution in 2 dimensions one has to find in how many ways one > can place 7 steps along the 3rd coordinate into the 15 available positions > (i.e., before the first two-dimensional step, after the last one, and in > between the 13 remaining inner positions). A three-dimensional path is of > the form {d1,d2,...,d21}, where each di represents a step to the right > (i.e., r), a step upwards (i.e., u}, or a step in the third direction (which > we call Y), say q. Thus a typical path could be e.g. > {q,r,r,u,q,q,u,u,u,r,r,q,q,q,u,r,u,u,r,q,r}, where there are 7 q's, 7 r's > and 7 u's. In this particular example this means one move in the direction > Y, two to the right, one upwards, two in direction Y, three upwards, etc. > This necessarily leads from the initial position to the final. Given the > configuration of the r's and u's, this particular path has one q before all > of them, two q's between the third and the fourth, three q's between the > eighth and the ninth, and one q between the thirteenth and the fourteenth. > For each two-dimensional configuration, the problem of how to place 7 q's > into the 15 available places is the so called "occupancy problem" of > combinatorial analysis. The number of arrangements (see e.g. Feller's > classical book on Probability Theory, Vol.1, Chapter II) for each > two-dimensional configuration is Binomial[21, 7] = 116280, and since there > are Binomial[14, 7] of those, the total number of paths for the > three-dimensional case is > > In[1]:= > Binomial[14, 7]*Binomial[21, 7] > Out[1]= > 399072960 > > Quite a large number! But the order of magnitude looks reasonable. I think > generalization to higher dimensional chessboards should not be too > difficult. > > Tomas Garza > Mexico City