Re: Re: Combinatorica questions!!!
- To: mathgroup at smc.vnet.net
- Subject: [mg20729] Re: [mg20656] Re: [mg20499] Combinatorica questions!!!
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Wed, 10 Nov 1999 00:17:44 -0500
- Sender: owner-wri-mathgroup at wolfram.com
> The solutions to the rook on the 3D chessboard by Rob Pratt
> and Andrzej Kozlowski assume that the rook only moves one unit in any direction at a time.
> But this is not how a rook moves, as Joinery in fact stated in the problem:
> > > > Example for allowable move:
> > > > Say from {0,0,0} to {0,6,0} but not {0,6,6},
> Therefore the generating function should be
> 1/(1-x/(1-x)-y/(1-y)-z/(1-z)) and the answer is the coefficient
> of x^7y^7z^7 which Mathematica gives as 75059524392.
>
> Arnold Knopfmacher and Helmut Prodinger
> Witwatersrand University
Arnold and Helmut,
I received one other message regarding the way a rook moves.
For purposes of counting the paths, I considered a rook move from (0,0,0)
to (0,6,0) as being composed of 6 unit steps in the y direction. Yes, the
rook takes these 6 steps all at once, but thinking of paths as being
composed of unit steps does not change the paths! There is a one-to-one
correspondence between paths composed of rook moves and the paths composed
of unit steps in the coordinate directions.
Your proposed generating function overcounts the paths. For example, the
path (0,0,0), (7,0,0), (7,7,0), (7,7,7) [3 rook moves, 21 unit steps]
shows up as
x^7 y^7 z^7
and x^1 x^6 y^7 z^7
and x^2 x^5 y^7 z^7
and x^2 x^5 y^4 y^2 z^7
and many other ways. In other words, consecutive moves in the same
direction aren't counted as one move. I suppose we have to be careful in
defining what a path is, but I don't think we want to count such things
multiple times and call them different paths.
Under the interpretation that a path is uniquely determined by the set
of cells it traverses, the original count Multinomial[7,7,7] = 399072960
is correct.
Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill
rpratt at email.unc.edu
http://www.unc.edu/~rpratt/