Re: Re: Combinatorica questions!!!
- To: mathgroup at smc.vnet.net
- Subject: [mg20599] Re: [mg20549] Re: [mg20499] Combinatorica questions!!!
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Tue, 2 Nov 1999 02:35:32 -0500
- Sender: owner-wri-mathgroup at wolfram.com
I just read Ed McBride's solution and realized that I was right the first
time but then (as often happens in combinatorial problems) when later
reading my solution got confused and sent unnecessary and wrong
"correction". The point is that in my confusing notation one step right (or
one step up) means not moving at all, so the moves of the type (right, up,
right, up, ...) ( or (up, right, up, right...)) actually give all the
possibilities and the correct answer is the orignal 3432, same as Ed's.
--
> From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
> Date: Sat, 30 Oct 1999 00:14:01 -0400
> To: mathgroup at smc.vnet.net
> Subject: [mg20599] [mg20549] Re: [mg20499] Combinatorica questions!!!
>
> 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: [mg20599] [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
> 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: [mg20599] [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.
>>>
>>>
>>>
>
>