MathGroup Archive 1999

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

Search the Archive

Re: Combinatorica questions!!!

  • To: mathgroup at smc.vnet.net
  • Subject: [mg20549] Re: [mg20499] Combinatorica questions!!!
  • From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
  • Date: Sat, 30 Oct 1999 00:14:01 -0400
  • Sender: owner-wri-mathgroup at wolfram.com

A small correction to my first answer. I wrongly stated that all solutions
can be assumed to be of the form
(right, up, right, up, ...).

There are, of course solutions of the form

( up, right, up, ...) .

If we do not consdier them the same, which they are really not according to
the rules of chess, then the totwl number of solutions must be double the
one I gave, i.e. 2* 3432=6864.

-- 


> From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
To: mathgroup at smc.vnet.net
> Date: Thu, 28 Oct 1999 16:30:28 +0900
> To: Keren Edwards <kedwards at cobol2java.com>, <mathgroup at smc.vnet.net>
> Subject: [mg20549] Re: [mg20499] Combinatorica questions!!!
> 
> These questions sound to me suspiciously like some sort of homework? Arn't
> they? I guess we should have some sort of policy here whether we should answer
> such questions...
> 
> Anyway, in the absence of any guidance I have decided that it is O.K. to
> answer such questions provided one uses Mathematica in doing so. 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. That
> means that we can assume that a path is determined by a sequence of moves:
> 
> (right, up, right, up, ...).
> 
> Let's call the length of such a path the number of right moves in it (which is
> half the total length of such a list). O.K., there is clearly only one path of
> length 1, which means the rook goes all the way to the right and then all the
> way to the top. Let's count the number of paths of length 2. First, let's
> calculate the number of different ways we can move from the bottom left hand
> corner to the bottom right hand corner in two steps. That's the same as the
> number of partitions of 8 into a sum of two positive integers,  counting
> partitions like 3+5 and 5+3 as different. This can be found as the coefficient
> of x^8 in the expression:
> 
> In[1]:=
> Coefficient[Sum[x^i, {i, 1, 8}]^2, x^8]
> Out[1]=
> 7
> 
> In other words, there are 7 different ways to get from the bottom left hand
> corner to the top left hand corner in two steps. Just to be sure let's list
> them:
> 
> {1,7},{7,1},{2,6},{6,2},{3,5},{5,3},{4,4}
> 
> Of course there is exactly the same number of ways to get from the bottom
> right hand corner to the top right hand corner in two steps. So the total
> number of ways to get from the bottom left hand corner to the top right hand
> corner in a path of length 2 is 7^2, i.e. 49 (each way of going from left to
> right can be paired with each way of going from bottom to top).
> 
> Similarly the number of ways of getting from the bottom left hand corner to
> the top right hand corner in a path of lenght 3 is
> 
> In[2]:=
> Coefficient[Sum[x^i, {i, 1, 8}]^3, x^8]
> Out[2]=
> 21
> 
> So the total number of ways (unless I have made some bad mistake somewhere)
> is:
> In[3]:=
> Sum[Coefficient[Sum[x^i, {i, 1, 8}]^j, x^8]^2, {j, 1, 8}]
> Out[3]=
> 3432
> 
> 
> The second question is much easier. A choice of 10 balls in your situation is
> exactly the same as a choice of an integer between 0 and 8, an integer betwen
> 0 and 9 and an integer between 0 and 7 so that the sum is 10. That's the same
> as the coeficient of x^10 in the following expression:
> In[5]:=
> Sum[x^i, {i, 0, 8}]*Sum[x^i, {i, 0, 9}]*Sum[x^i, {i, 0, 7}] // Expand
> Out[5]=
> 2       3       4       5       6       7
> 1 + 3 x + 6 x  + 10 x  + 15 x  + 21 x  + 28 x  + 36 x  +
> 
> 8       9       10       11       12       13
> 44 x  + 51 x  + 56 x   + 59 x   + 60 x   + 59 x   +
> 
> 14       15       16       17       18       19
> 56 x   + 51 x   + 44 x   + 36 x   + 28 x   + 21 x   +
> 
> 20       21      22      23    24
> 15 x   + 10 x   + 6 x   + 3 x   + x
> 
> As you can see it is 56. (One could also just get the answer using the
> function Coefficient). In part 2 you require that each color be chosen at
> least one. That means that we want to know
> 
> In[6]:=
> Coefficient[Sum[x^i, {i, 1, 8}]*Sum[x^i, {i, 1, 9}]*Sum[x^i, {i, 1, 7}], x^10]
> Out[6]=
> 35
> 
> 
> -- 
> Andrzej Kozlowski
> Toyama International University
> JAPAN
> http://sigma.tuins.ac.jp
> 
> 
>> From: "Keren Edwards" <kedwards at cobol2java.com>
To: mathgroup at smc.vnet.net
>> Organization: NetVision Israel
>> Date: Wed, 27 Oct 1999 02:04:59 -0400
>> To: mathgroup at smc.vnet.net
>> Subject: [mg20549] [mg20499] Combinatorica questions!!!
>> 
>> Hi all!!
>> 
>> 2 different questions:
>> 
>> 1.    how many ways does a castle have to reach from the bottom left side
>> corner
>> of a chess board to the upper right corner of the board if he can
>> move right
>> and up only?
>> 
>> 
>> 
>> 2.     you have 8 red identical balls, 9 purple identical balls and 7 white
>> identical ones.
>> a.  How many ways can you choose 10 balls with no matter to the
>> order of the balls?
>> b.  How many ways can you choose 10 balls with no matter to the
>> order of the balls, if each color must
>> be chosen once at least?
>> 
>> 
>> 
>> Many thanx.
>> 
>> 
>> 



  • Prev by Date: Electromagnetics notebooks
  • Next by Date: Corrupt Notebook
  • Previous by thread: Combinatorica questions!!!
  • Next by thread: Re: Combinatorica questions!!!