MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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/
> 
> 



  • Prev by Date: Re: the new @@@ thing, MapApply?
  • Next by Date: Re: Mathsource File
  • Previous by thread: Re: Re: Combinatorica questions!!!
  • Next by thread: Re: Re: Combinatorica questions!!!