Re: Re: Combinatorica questions!!!
- To: mathgroup at smc.vnet.net
- Subject: [mg20733] Re: [mg20645] Re: [mg20499] Combinatorica questions!!!
- From: "Tomas Garza" <tgarza at mail.internet.com.mx>
- Date: Wed, 10 Nov 1999 00:17:46 -0500
- Sender: owner-wri-mathgroup at wolfram.com
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