Re: Re: Combinatorica questions!!!
- To: mathgroup at smc.vnet.net
- Subject: [mg20730] Re: [mg20656] Re: [mg20499] Combinatorica questions!!!
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Wed, 10 Nov 1999 00:17:44 -0500
- Sender: owner-wri-mathgroup at wolfram.com
I considered the same point in my first answer to the original question of
Karen Edwards. Here is the beginning of that answer:
> So let's start with the first. By a castle I assume you mean the chess piece
> that is normally in English called a rook. The question is not completely
> clear in that yo do not explain whether you want to count the number of
> distinct moves or distinct paths a rook must follow to get from the bottom
> left hand corner to the upper right hand corner. I assume you mean the number
> of paths.
--
> From: Rob Pratt <rpratt at email.unc.edu>
> Reply-To: Rob Pratt <rpratt at email.unc.edu>
> Date: Mon, 8 Nov 1999 14:20:59 -0500 (EST)
> To: Arnold Knopfmacher <arnoldk at cam.wits.ac.za>
> Cc: mathgroup at smc.vnet.net, andrzej at tuins.ac.jp
> Subject: [mg20730] Re: [mg20656] Re: [mg20499] Combinatorica questions!!!
>
>> 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/
>
>