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