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