Re: Combinatorica questions!!!
- To: mathgroup at smc.vnet.net
- Subject: [mg20545] Re: [mg20499] Combinatorica questions!!!
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Sat, 30 Oct 1999 00:13:59 -0400
- Sender: owner-wri-mathgroup at wolfram.com
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: [mg20545] [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. > > >